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 "drizzled/internal/my_bit.h"
57
#include "drizzled/internal/my_sys.h"
58
#include "drizzled/internal/iocache.h"
63
using namespace drizzled;
65
extern drizzled::plugin::StorageEngine *heap_engine;
66
extern std::bitset<12> test_flags;
68
/** Declarations of static functions used in this source file. */
69
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
70
static void calc_group_buffer(JOIN *join,order_st *group);
71
static bool alloc_group_fields(JOIN *join,order_st *group);
72
static uint32_t cache_record_length(JOIN *join, uint32_t index);
73
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
74
static bool get_best_combination(JOIN *join);
75
static void set_position(JOIN *join,
78
optimizer::KeyUse *key);
79
static bool choose_plan(JOIN *join,table_map join_tables);
80
static void best_access_path(JOIN *join, JoinTable *s,
82
table_map remaining_tables,
86
static void optimize_straight_join(JOIN *join, table_map join_tables);
87
static bool greedy_search(JOIN *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
88
static bool best_extension_by_limited_search(JOIN *join,
89
table_map remaining_tables,
94
uint32_t prune_level);
95
static uint32_t determine_search_depth(JOIN* join);
96
static bool make_simple_join(JOIN *join,Table *tmp_table);
97
static void make_outerjoin_info(JOIN *join);
98
static bool make_join_select(JOIN *join, optimizer::SqlSelect *select,COND *item);
99
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
100
static void update_depend_map(JOIN *join);
101
static void update_depend_map(JOIN *join, order_st *order);
102
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond, bool change_list, bool *simple_order);
103
static int return_zero_rows(JOIN *join,
108
uint64_t select_options,
111
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top);
112
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields, Item *having);
113
static int setup_without_group(Session *session,
114
Item **ref_pointer_array,
118
List<Item> &all_fields,
122
bool *hidden_group_fields);
123
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
124
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
125
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
126
static void reset_nj_counters(List<TableList> *join_list);
127
static bool test_if_subpart(order_st *a,order_st *b);
128
static void restore_prev_nj_state(JoinTable *last);
129
static uint32_t make_join_orderinfo(JOIN *join);
130
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
131
static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
134
Prepare of whole select (including sub queries in future).
137
Add check of calculation of GROUP functions and fields:
138
SELECT COUNT(*)+table.col1 from table1;
145
int JOIN::prepare(Item ***rref_pointer_array,
146
TableList *tables_init,
150
order_st *order_init,
151
order_st *group_init,
153
Select_Lex *select_lex_arg,
154
Select_Lex_Unit *unit_arg)
156
// to prevent double initialization on EXPLAIN
162
group_list= group_init;
164
tables_list= tables_init;
165
select_lex= select_lex_arg;
166
select_lex->join= this;
167
join_list= &select_lex->top_join_list;
168
union_part= unit_arg->is_union();
170
session->lex->current_select->is_item_list_lookup= 1;
172
If we have already executed SELECT, then it have not sense to prevent
173
its table from update (see unique_table())
175
if (session->derived_tables_processing)
176
select_lex->exclude_from_table_unique_test= true;
178
/* Check that all tables, fields, conds and order are ok */
180
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
181
setup_tables_and_check_access(session, &select_lex->context, join_list,
182
tables_list, &select_lex->leaf_tables,
186
TableList *table_ptr;
187
for (table_ptr= select_lex->leaf_tables;
189
table_ptr= table_ptr->next_leaf)
192
if (setup_wild(session, fields_list, &all_fields, wild_num) ||
193
select_lex->setup_ref_array(session, og_num) ||
194
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
196
setup_without_group(session, (*rref_pointer_array), tables_list,
197
select_lex->leaf_tables, fields_list,
198
all_fields, &conds, order, group_list,
199
&hidden_group_fields))
202
ref_pointer_array= *rref_pointer_array;
206
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
207
session->where="having clause";
208
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
209
select_lex->having_fix_field= 1;
210
bool having_fix_rc= (!having->fixed &&
211
(having->fix_fields(session, &having) ||
212
having->check_cols(1)));
213
select_lex->having_fix_field= 0;
214
if (having_fix_rc || session->is_error())
216
session->lex->allow_sum_func= save_allow_sum_func;
220
Item_subselect *subselect;
221
Item_in_subselect *in_subs= NULL;
223
Are we in a subquery predicate?
224
TODO: the block below will be executed for every PS execution without need.
226
if ((subselect= select_lex->master_unit()->item))
228
if (subselect->substype() == Item_subselect::IN_SUBS)
229
in_subs= (Item_in_subselect*)subselect;
232
bool do_materialize= !test(session->variables.optimizer_switch &
233
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
235
Check if the subquery predicate can be executed via materialization.
236
The required conditions are:
237
1. Subquery predicate is an IN/=ANY subq predicate
238
2. Subquery is a single SELECT (not a UNION)
239
3. Subquery is not a table-less query. In this case there is no
240
point in materializing.
241
4. Subquery predicate is a top-level predicate
242
(this implies it is not negated)
243
TODO: this is a limitation that should be lifeted once we
244
implement correct NULL semantics (WL#3830)
245
5. Subquery is non-correlated
247
This is an overly restrictive condition. It can be extended to:
248
(Subquery is non-correlated ||
249
Subquery is correlated to any query outer to IN predicate ||
250
(Subquery is correlated to the immediate outer query &&
251
Subquery !contains {GROUP BY, order_st BY [LIMIT],
252
aggregate functions) && subquery predicate is not under "NOT IN"))
253
6. No execution method was already chosen (by a prepared statement).
255
(*) The subquery must be part of a SELECT statement. The current
256
condition also excludes multi-table update statements.
258
We have to determine whether we will perform subquery materialization
259
before calling the IN=>EXISTS transformation, so that we know whether to
260
perform the whole transformation or only that part of it which wraps
261
Item_in_subselect in an Item_in_optimizer.
263
if (do_materialize &&
265
!select_lex->master_unit()->first_select()->next_select() && // 2
266
select_lex->master_unit()->first_select()->leaf_tables && // 3
267
session->lex->sql_command == SQLCOM_SELECT) // *
269
if (in_subs->is_top_level_item() && // 4
270
!in_subs->is_correlated && // 5
271
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
272
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
275
Item_subselect::trans_res trans_res;
276
if ((trans_res= subselect->select_transformer(this)) !=
277
Item_subselect::RES_OK)
279
return((trans_res == Item_subselect::RES_ERROR));
288
for (ord= order; ord; ord= ord->next)
290
Item *item= *ord->item;
291
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
292
item->split_sum_func(session, ref_pointer_array, all_fields);
296
if (having && having->with_sum_func)
297
having->split_sum_func(session, ref_pointer_array, all_fields,
299
if (select_lex->inner_sum_func_list)
301
Item_sum *end=select_lex->inner_sum_func_list;
302
Item_sum *item_sum= end;
305
item_sum= item_sum->next;
306
item_sum->split_sum_func(session, ref_pointer_array,
307
all_fields, item_sum->ref_by, false);
308
} while (item_sum != end);
311
if (select_lex->inner_refs_list.elements &&
312
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
316
Check if there are references to un-aggregated columns when computing
317
aggregate functions with implicit grouping (there is no GROUP BY).
319
MODE_ONLY_FULL_GROUP_BY is enabled here by default
322
select_lex->full_group_by_flag.test(NON_AGG_FIELD_USED) &&
323
select_lex->full_group_by_flag.test(SUM_FUNC_USED))
325
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
326
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
330
/* Caclulate the number of groups */
332
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
339
if (result && result->prepare(fields_list, unit_arg))
342
/* Init join struct */
343
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
344
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
345
this->group= group_list != 0;
348
#ifdef RESTRICTED_GROUP
349
if (sum_func_count && !group_list && (func_count || field_count))
351
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
355
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
357
if (alloc_func_list())
367
Remove the predicates pushed down into the subquery
370
JOIN::remove_subq_pushed_predicates()
371
where IN Must be NULL
372
OUT The remaining WHERE condition, or NULL
375
Given that this join will be executed using (unique|index)_subquery,
376
without "checking NULL", remove the predicates that were pushed down
379
If the subquery compares scalar values, we can remove the condition that
380
was wrapped into trig_cond (it will be checked when needed by the subquery
383
If the subquery compares row values, we need to keep the wrapped
384
equalities in the WHERE clause: when the left (outer) tuple has both NULL
385
and non-NULL values, we'll do a full table scan and will rely on the
386
equalities corresponding to non-NULL parts of left tuple to filter out
387
non-matching records.
389
TODO: We can remove the equalities that will be guaranteed to be true by the
390
fact that subquery engine will be using index lookup. This must be done only
391
for cases where there are no conversion errors of significance, e.g. 257
392
that is searched in a byte. But this requires homogenization of the return
393
codes of all Field*::store() methods.
395
void JOIN::remove_subq_pushed_predicates(Item **where)
397
if (conds->type() == Item::FUNC_ITEM &&
398
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
399
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
400
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
401
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
402
((Item_func *)conds)->arguments()[0]))
410
global select optimisation.
413
error code saved in field 'error'
422
// to prevent double initialization on EXPLAIN
427
session->set_proc_info("optimizing");
428
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
429
unit->select_limit_cnt);
430
/* select_limit is used to decide if we are likely to scan the whole table */
431
select_limit= unit->select_limit_cnt;
432
if (having || (select_options & OPTION_FOUND_ROWS))
433
select_limit= HA_POS_ERROR;
434
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
435
// Ignore errors of execution if option IGNORE present
436
if (session->lex->ignore)
437
session->lex->current_select->no_error= 1;
439
#ifdef HAVE_REF_TO_FIELDS // Not done yet
440
/* Add HAVING to WHERE if possible */
441
if (having && !group_list && !sum_func_count)
448
else if ((conds=new Item_cond_and(conds,having)))
451
Item_cond_and can't be fixed after creation, so we do not check
454
conds->fix_fields(session, &conds);
455
conds->change_ref_to_fields(session, tables_list);
456
conds->top_level_item();
462
/* Convert all outer joins to inner joins if possible */
463
conds= simplify_joins(this, join_list, conds, true);
464
build_bitmap_for_nested_joins(join_list, 0);
466
conds= optimize_cond(this, conds, join_list, &cond_value);
467
if (session->is_error())
474
having= optimize_cond(this, having, join_list, &having_value);
475
if (session->is_error())
480
if (select_lex->where)
481
select_lex->cond_value= cond_value;
482
if (select_lex->having)
483
select_lex->having_value= having_value;
485
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
486
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
487
{ /* Impossible cond */
488
zero_result_cause= having_value == Item::COND_FALSE ?
489
"Impossible HAVING" : "Impossible WHERE";
495
/* Optimize count(*), cmin() and cmax() */
496
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
500
optimizer::sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
501
to the WHERE conditions,
502
or 1 if all items were resolved,
503
or 0, or an error number HA_ERR_...
505
if ((res= optimizer::sum_query(select_lex->leaf_tables, all_fields, conds)))
507
if (res == HA_ERR_KEY_NOT_FOUND)
509
zero_result_cause= "No matching min/max row";
520
zero_result_cause= "No matching min/max row";
524
zero_result_cause= "Select tables optimized away";
525
tables_list= 0; // All tables resolved
527
Extract all table-independent conditions and replace the WHERE
528
clause with them. All other conditions were computed by optimizer::sum_query
529
and the MIN/MAX/COUNT function(s) have been replaced by constants,
530
so there is no need to compute the whole WHERE clause again.
531
Notice that make_cond_for_table() will always succeed to remove all
532
computed conditions, because optimizer::sum_query() is applicable only to
534
Preserve conditions for EXPLAIN.
536
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
538
COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
539
conds= table_independent_conds;
548
error= -1; // Error is sent to client
549
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
551
/* Calculate how to do the join */
552
session->set_proc_info("statistics");
553
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
554
session->is_fatal_error)
559
/* Remove distinct if only const tables */
560
select_distinct= select_distinct && (const_tables != tables);
561
session->set_proc_info("preparing");
562
if (result->initialize_tables(this))
564
return 1; // error == -1
566
if (const_table_map != found_const_table_map &&
567
!(select_options & SELECT_DESCRIBE) &&
569
!(conds->used_tables() & RAND_TABLE_BIT) ||
570
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
572
zero_result_cause= "no matching row in const table";
576
if (!(session->options & OPTION_BIG_SELECTS) &&
577
best_read > (double) session->variables.max_join_size &&
578
!(select_options & SELECT_DESCRIBE))
580
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
584
if (const_tables && !(select_options & SELECT_NO_UNLOCK))
585
mysql_unlock_some_tables(session, table, const_tables);
586
if (!conds && outer_join)
588
/* Handle the case where we have an OUTER JOIN without a WHERE */
589
conds=new Item_int((int64_t) 1,1); // Always true
591
select= optimizer::make_select(*table, const_table_map,
592
const_table_map, conds, 1, &error);
599
reset_nj_counters(join_list);
600
make_outerjoin_info(this);
603
Among the equal fields belonging to the same multiple equality
604
choose the one that is to be retrieved first and substitute
605
all references to these in where condition for a reference for
610
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
611
conds->update_used_tables();
615
Permorm the the optimization on fields evaluation mentioned above
616
for all on expressions.
618
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
620
if (*tab->on_expr_ref)
622
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
625
(*tab->on_expr_ref)->update_used_tables();
629
if (conds &&!outer_join && const_table_map != found_const_table_map &&
630
(select_options & SELECT_DESCRIBE) &&
631
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
633
conds=new Item_int((int64_t) 0,1); // Always false
636
if (make_join_select(this, select, conds))
639
"Impossible WHERE noticed after reading const tables";
640
return(0); // error == 0
643
error= -1; /* if goto err */
645
/* Optimize distinct away if possible */
647
order_st *org_order= order;
648
order= remove_constants(this, order,conds,1, &simple_order);
649
if (session->is_error())
656
If we are using order_st BY NULL or order_st BY const_expression,
657
return result in any order (even if we are using a GROUP BY)
659
if (!order && org_order)
663
Check if we can optimize away GROUP BY/DISTINCT.
664
We can do that if there are no aggregate functions, the
665
fields in DISTINCT clause (if present) and/or columns in GROUP BY
666
(if present) contain direct references to all key parts of
667
an unique index (in whatever order) and if the key parts of the
668
unique index cannot contain NULLs.
669
Note that the unique keys for DISTINCT and GROUP BY should not
670
be the same (as long as they are unique).
672
The FROM clause must contain a single non-constant table.
674
if (tables - const_tables == 1 && (group_list || select_distinct) &&
675
! tmp_table_param.sum_func_count &&
676
(! join_tab[const_tables].select ||
677
! join_tab[const_tables].select->quick ||
678
join_tab[const_tables].select->quick->get_type() !=
679
optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))
681
if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
684
We have found that grouping can be removed since groups correspond to
685
only one row anyway, but we still have to guarantee correct result
686
order. The line below effectively rewrites the query from GROUP BY
687
<fields> to order_st BY <fields>. There are two exceptions:
688
- if skip_sort_order is set (see above), then we can simply skip
690
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
691
with the GROUP BY ones, i.e. either one is a prefix of another.
692
We only check if the order_st BY is a prefix of GROUP BY. In this case
693
test_if_subpart() copies the ASC/DESC attributes from the original
695
If GROUP BY is a prefix of order_st BY, then it is safe to leave
698
if (! order || test_if_subpart(group_list, order))
699
order= skip_sort_order ? 0 : group_list;
701
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
702
rewritten to IGNORE INDEX FOR order_st BY(fields).
704
join_tab->table->keys_in_use_for_order_by=
705
join_tab->table->keys_in_use_for_group_by;
709
if (select_distinct &&
710
list_contains_unique_index(join_tab[const_tables].table,
711
find_field_in_item_list,
712
(void *) &fields_list))
717
if (group_list || tmp_table_param.sum_func_count)
719
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
722
else if (select_distinct && tables - const_tables == 1)
725
We are only using one table. In this case we change DISTINCT to a
727
- The GROUP BY can be done through indexes (no sort) and the order_st
728
BY only uses selected fields.
729
(In this case we can later optimize away GROUP BY and order_st BY)
730
- We are scanning the whole table without LIMIT
732
- We are using CALC_FOUND_ROWS
733
- We are using an order_st BY that can't be optimized away.
735
We don't want to use this optimization when we are using LIMIT
736
because in this case we can just create a temporary table that
737
holds LIMIT rows and stop when this table is full.
739
JoinTable *tab= &join_tab[const_tables];
740
bool all_order_fields_used;
742
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
743
&tab->table->keys_in_use_for_order_by);
744
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
745
order, fields_list, all_fields,
746
&all_order_fields_used)))
748
bool skip_group= (skip_sort_order &&
749
test_if_skip_sort_order(tab, group_list, select_limit, 1,
750
&tab->table->keys_in_use_for_group_by) != 0);
751
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
752
if ((skip_group && all_order_fields_used) ||
753
select_limit == HA_POS_ERROR ||
754
(order && !skip_sort_order))
756
/* Change DISTINCT to GROUP BY */
759
if (all_order_fields_used)
761
if (order && skip_sort_order)
764
Force MySQL to read the table in sorted order to get result in
767
tmp_table_param.quick_group=0;
771
group=1; // For end_write_group
776
else if (session->is_fatal_error) // End of memory
781
order_st *old_group_list;
782
group_list= remove_constants(this, (old_group_list= group_list), conds,
783
rollup.state == ROLLUP::STATE_NONE,
785
if (session->is_error())
790
if (old_group_list && !group_list)
793
if (!group_list && group)
795
order=0; // The output has only one row
797
select_distinct= 0; // No need in distinct for 1 row
798
group_optimized_away= 1;
801
calc_group_buffer(this, group_list);
802
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
804
if (test_if_subpart(group_list, order) ||
805
(!group_list && tmp_table_param.sum_func_count))
808
// Can't use sort on head table if using row cache
818
Check if we need to create a temporary table.
819
This has to be done if all tables are not already read (const tables)
820
and one of the following conditions holds:
821
- We are using DISTINCT (simple distinct's are already optimized away)
822
- We are using an order_st BY or GROUP BY on fields not in the first table
823
- We are using different order_st BY and GROUP BY orders
824
- The user wants us to buffer the result.
826
need_tmp= (const_tables != tables &&
827
((select_distinct || !simple_order || !simple_group) ||
828
(group_list && order) ||
829
test(select_options & OPTION_BUFFER_RESULT)));
831
uint32_t no_jbuf_after= make_join_orderinfo(this);
832
uint64_t select_opts_for_readinfo=
833
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
835
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
836
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
839
/* Create all structures needed for materialized subquery execution. */
840
if (setup_subquery_materialization())
843
/* Cache constant expressions in WHERE, HAVING, ON clauses. */
847
is this simple IN subquery?
849
if (!group_list && !order &&
850
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
851
tables == 1 && conds &&
857
if (join_tab[0].type == AM_EQ_REF && join_tab[0].ref.items[0]->name == in_left_expr_name)
859
remove_subq_pushed_predicates(&where);
860
save_index_subquery_explain_info(join_tab, where);
861
join_tab[0].type= AM_UNIQUE_SUBQUERY;
865
subselect_uniquesubquery_engine(session,
870
else if (join_tab[0].type == AM_REF &&
871
join_tab[0].ref.items[0]->name == in_left_expr_name)
873
remove_subq_pushed_predicates(&where);
874
save_index_subquery_explain_info(join_tab, where);
875
join_tab[0].type= AM_INDEX_SUBQUERY;
879
subselect_indexsubquery_engine(session,
887
else if (join_tab[0].type == AM_REF_OR_NULL &&
888
join_tab[0].ref.items[0]->name == in_left_expr_name &&
889
having->name == in_having_cond)
891
join_tab[0].type= AM_INDEX_SUBQUERY;
893
conds= remove_additional_cond(conds);
894
save_index_subquery_explain_info(join_tab, conds);
896
change_engine(new subselect_indexsubquery_engine(session,
906
Need to tell handlers that to play it safe, it should fetch all
907
columns of the primary key of the tables: this is because MySQL may
908
build row pointers for the rows, and for all columns of the primary key
909
the read set has not necessarily been set by the server code.
911
if (need_tmp || select_distinct || group_list || order)
913
for (uint32_t i = const_tables; i < tables; i++)
914
join_tab[i].table->prepare_for_position();
917
if (const_tables != tables)
920
Because filesort always does a full table scan or a quick range scan
921
we must add the removed reference to the select for the table.
922
We only need to do this when we have a simple_order or simple_group
923
as in other cases the join is done before the sort.
925
if ((order || group_list) &&
926
(join_tab[const_tables].type != AM_ALL) &&
927
(join_tab[const_tables].type != AM_REF_OR_NULL) &&
928
((order && simple_order) || (group_list && simple_group)))
930
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
935
if (!(select_options & SELECT_BIG_RESULT) &&
938
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
939
unit->select_limit_cnt, 0,
940
&join_tab[const_tables].table->
941
keys_in_use_for_group_by))) ||
943
tmp_table_param.quick_group)
945
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
950
Force using of tmp table if sorting by a SP or UDF function due to
951
their expensive and probably non-deterministic nature.
953
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
955
Item *item= *tmp_order->item;
956
if (item->is_expensive())
958
/* Force tmp table without sort */
959
need_tmp=1; simple_order=simple_group=0;
967
if (select_options & SELECT_DESCRIBE)
975
The loose index scan access method guarantees that all grouping or
976
duplicate row elimination (for distinct) is already performed
977
during data retrieval, and that all MIN/MAX functions are already
978
computed for each group. Thus all MIN/MAX functions should be
979
treated as regular functions, and there is no need to perform
980
grouping in the main execution loop.
981
Notice that currently loose index scan is applicable only for
982
single table queries, thus it is sufficient to test only the first
983
join_tab element of the plan for its access method.
985
if (join_tab->is_using_loose_index_scan())
986
tmp_table_param.precomputed_group_by= true;
988
/* Create a tmp table if distinct or if the sort is too complicated */
991
session->set_proc_info("Creating tmp table");
993
init_items_ref_array();
995
tmp_table_param.hidden_field_count= (all_fields.elements -
996
fields_list.elements);
997
order_st *tmp_group= ((!simple_group &&
998
! (test_flags.test(TEST_NO_KEY_GROUP))) ? group_list :
1001
Pushing LIMIT to the temporary table creation is not applicable
1002
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1003
there are aggregate functions, because in all these cases we need
1006
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1008
!session->lex->current_select->with_sum_func) ?
1009
select_limit : HA_POS_ERROR;
1011
if (!(exec_tmp_table1=
1012
create_tmp_table(session, &tmp_table_param, all_fields,
1014
group_list ? 0 : select_distinct,
1015
group_list && simple_group,
1024
We don't have to store rows in temp table that doesn't match HAVING if:
1025
- we are sorting the table and writing complete group rows to the
1027
- We are using DISTINCT without resolving the distinct as a GROUP BY
1030
If having is not handled here, it will be checked before the row
1031
is sent to the client.
1033
if (tmp_having && (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1036
/* if group or order on first table, sort first */
1037
if (group_list && simple_group)
1039
session->set_proc_info("Sorting for group");
1040
if (create_sort_index(session, this, group_list,
1041
HA_POS_ERROR, HA_POS_ERROR, false) ||
1042
alloc_group_fields(this, group_list) ||
1043
make_sum_func_list(all_fields, fields_list, 1) ||
1044
setup_sum_funcs(session, sum_funcs))
1052
if (make_sum_func_list(all_fields, fields_list, 0) ||
1053
setup_sum_funcs(session, sum_funcs))
1058
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1060
session->set_proc_info("Sorting for order");
1061
if (create_sort_index(session, this, order,
1062
HA_POS_ERROR, HA_POS_ERROR, true))
1071
Optimize distinct when used on some of the tables
1072
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1073
In this case we can stop scanning t2 when we have found one t1.a
1076
if (exec_tmp_table1->distinct)
1078
table_map used_tables= session->used_tables;
1079
JoinTable *last_join_tab= join_tab+tables-1;
1082
if (used_tables & last_join_tab->table->map)
1084
last_join_tab->not_used_in_distinct=1;
1085
} while (last_join_tab-- != join_tab);
1086
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1087
if (order && skip_sort_order)
1089
/* Should always succeed */
1090
if (test_if_skip_sort_order(&join_tab[const_tables],
1091
order, unit->select_limit_cnt, 0,
1092
&join_tab[const_tables].table->
1093
keys_in_use_for_order_by))
1099
If this join belongs to an uncacheable subquery save
1102
if (select_lex->uncacheable && !is_top_level_join() &&
1103
init_save_join_tab())
1112
Restore values in temporary join.
1114
void JOIN::restore_tmp()
1116
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1121
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1122
select_lex->offset_limit->val_uint() :
1127
if (exec_tmp_table1)
1129
exec_tmp_table1->cursor->extra(HA_EXTRA_RESET_STATE);
1130
exec_tmp_table1->cursor->ha_delete_all_rows();
1131
exec_tmp_table1->free_io_cache();
1132
exec_tmp_table1->filesort_free_buffers();
1134
if (exec_tmp_table2)
1136
exec_tmp_table2->cursor->extra(HA_EXTRA_RESET_STATE);
1137
exec_tmp_table2->cursor->ha_delete_all_rows();
1138
exec_tmp_table2->free_io_cache();
1139
exec_tmp_table2->filesort_free_buffers();
1142
set_items_ref_array(items0);
1145
memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);
1150
/* Reset of sum functions */
1153
Item_sum *func, **func_ptr= sum_funcs;
1154
while ((func= *(func_ptr++)))
1162
@brief Save the original join layout
1164
@details Saves the original join layout so it can be reused in
1165
re-execution and for EXPLAIN.
1167
@return Operation status
1169
@retval 1 error occurred.
1171
bool JOIN::init_save_join_tab()
1173
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
1175
error= 0; // Ensure that tmp_join.error= 0
1180
bool JOIN::save_join_tab()
1182
if (!join_tab_save && select_lex->master_unit()->uncacheable)
1184
if (!(join_tab_save= (JoinTable*)session->memdup((unsigned char*) join_tab,
1185
sizeof(JoinTable) * tables)))
1195
Note, that create_sort_index calls test_if_skip_sort_order and may
1196
finally replace sorting with index scan if there is a LIMIT clause in
1197
the query. It's never shown in EXPLAIN!
1200
When can we have here session->net.report_error not zero?
1204
List<Item> *columns_list= &fields_list;
1207
session->set_proc_info("executing");
1210
if (!tables_list && (tables || !select_lex->with_sum_func))
1212
/* Only test of functions */
1213
if (select_options & SELECT_DESCRIBE)
1215
optimizer::ExplainPlan planner(this,
1219
(zero_result_cause ? zero_result_cause : "No tables used"));
1220
planner.printPlan();
1224
result->send_fields(*columns_list);
1226
We have to test for 'conds' here as the WHERE may not be constant
1227
even if we don't have any tables for prepared statements or if
1228
conds uses something like 'rand()'.
1230
if (cond_value != Item::COND_FALSE &&
1231
(!conds || conds->val_int()) &&
1232
(!having || having->val_int()))
1234
if (do_send_rows && result->send_data(fields_list))
1238
error= (int) result->send_eof();
1239
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
1244
error= (int) result->send_eof();
1248
/* Single select (without union) always returns 0 or 1 row */
1249
session->limit_found_rows= send_records;
1250
session->examined_row_count= 0;
1254
Don't reset the found rows count if there're no tables as
1255
FOUND_ROWS() may be called. Never reset the examined row count here.
1256
It must be accumulated from all join iterations of all join parts.
1259
session->limit_found_rows= 0;
1261
if (zero_result_cause)
1263
(void) return_zero_rows(this, result, select_lex->leaf_tables,
1265
send_row_on_empty_set(),
1272
if (select_options & SELECT_DESCRIBE)
1275
Check if we managed to optimize order_st BY away and don't use temporary
1276
table to resolve order_st BY: in that case, we only may need to do
1277
filesort for GROUP BY.
1279
if (!order && !no_order && (!skip_sort_order || !need_tmp))
1281
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
1283
simple_order= simple_group;
1286
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
1288
if (const_tables == tables
1289
|| ((simple_order || skip_sort_order)
1290
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
1294
optimizer::ExplainPlan planner(this,
1296
order != 0 && ! skip_sort_order,
1298
! tables ? "No tables used" : NULL);
1299
planner.printPlan();
1303
JOIN *curr_join= this;
1304
List<Item> *curr_all_fields= &all_fields;
1305
List<Item> *curr_fields_list= &fields_list;
1306
Table *curr_tmp_table= 0;
1308
Initialize examined rows here because the values from all join parts
1309
must be accumulated in examined_row_count. Hence every join
1310
iteration must count from zero.
1312
curr_join->examined_rows= 0;
1314
/* Create a tmp table if distinct or if the sort is too complicated */
1320
We are in a non cacheable sub query. Get the saved join structure
1322
(curr_join may have been modified during last exection and we need
1325
curr_join= tmp_join;
1327
curr_tmp_table= exec_tmp_table1;
1329
/* Copy data to the temporary table */
1330
session->set_proc_info("Copying to tmp table");
1331
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
1332
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1333
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1338
curr_tmp_table->cursor->info(HA_STATUS_VARIABLE);
1340
if (curr_join->having)
1341
curr_join->having= curr_join->tmp_having= 0; // Allready done
1343
/* Change sum_fields reference to calculated fields in tmp_table */
1344
curr_join->all_fields= *curr_all_fields;
1347
items1= items0 + all_fields.elements;
1348
if (sort_and_group || curr_tmp_table->group)
1350
if (change_to_use_tmp_fields(session, items1,
1351
tmp_fields_list1, tmp_all_fields1,
1352
fields_list.elements, all_fields))
1357
if (change_refs_to_tmp_fields(session, items1,
1358
tmp_fields_list1, tmp_all_fields1,
1359
fields_list.elements, all_fields))
1362
curr_join->tmp_all_fields1= tmp_all_fields1;
1363
curr_join->tmp_fields_list1= tmp_fields_list1;
1364
curr_join->items1= items1;
1366
curr_all_fields= &tmp_all_fields1;
1367
curr_fields_list= &tmp_fields_list1;
1368
curr_join->set_items_ref_array(items1);
1370
if (sort_and_group || curr_tmp_table->group)
1372
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
1373
+ curr_join->tmp_table_param.func_count;
1374
curr_join->tmp_table_param.sum_func_count= 0;
1375
curr_join->tmp_table_param.func_count= 0;
1379
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
1380
curr_join->tmp_table_param.func_count= 0;
1383
if (curr_tmp_table->group)
1384
{ // Already grouped
1385
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
1386
curr_join->order= curr_join->group_list; /* order by group */
1387
curr_join->group_list= 0;
1391
If we have different sort & group then we must sort the data by group
1392
and copy it to another tmp table
1393
This code is also used if we are using distinct something
1394
we haven't been able to store in the temporary table yet
1395
like SEC_TO_TIME(SUM(...)).
1398
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
1399
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
1400
{ /* Must copy to another table */
1401
/* Free first data from old join */
1402
curr_join->join_free();
1403
if (make_simple_join(curr_join, curr_tmp_table))
1405
calc_group_buffer(curr_join, group_list);
1406
count_field_types(select_lex, &curr_join->tmp_table_param,
1407
curr_join->tmp_all_fields1,
1408
curr_join->select_distinct && !curr_join->group_list);
1409
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
1410
- curr_join->tmp_fields_list1.elements;
1412
if (exec_tmp_table2)
1413
curr_tmp_table= exec_tmp_table2;
1416
/* group data to new table */
1419
If the access method is loose index scan then all MIN/MAX
1420
functions are precomputed, and should be treated as regular
1421
functions. See extended comment in JOIN::exec.
1423
if (curr_join->join_tab->is_using_loose_index_scan())
1424
curr_join->tmp_table_param.precomputed_group_by= true;
1426
if (!(curr_tmp_table=
1427
exec_tmp_table2= create_tmp_table(session,
1428
&curr_join->tmp_table_param,
1431
curr_join->select_distinct &&
1432
!curr_join->group_list,
1433
1, curr_join->select_options,
1437
curr_join->exec_tmp_table2= exec_tmp_table2;
1439
if (curr_join->group_list)
1441
session->set_proc_info("Creating sort index");
1442
if (curr_join->join_tab == join_tab && save_join_tab())
1446
if (create_sort_index(session, curr_join, curr_join->group_list,
1447
HA_POS_ERROR, HA_POS_ERROR, false) ||
1448
make_group_fields(this, curr_join))
1452
sortorder= curr_join->sortorder;
1455
session->set_proc_info("Copying to group table");
1457
if (curr_join != this)
1461
curr_join->sum_funcs= sum_funcs2;
1462
curr_join->sum_funcs_end= sum_funcs_end2;
1466
curr_join->alloc_func_list();
1467
sum_funcs2= curr_join->sum_funcs;
1468
sum_funcs_end2= curr_join->sum_funcs_end;
1471
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
1473
curr_join->group_list= 0;
1475
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
1476
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1478
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
1479
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1484
end_read_record(&curr_join->join_tab->read_record);
1485
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1486
curr_join->join_tab[0].table= 0; // Table is freed
1488
// No sum funcs anymore
1491
items2= items1 + all_fields.elements;
1492
if (change_to_use_tmp_fields(session, items2,
1493
tmp_fields_list2, tmp_all_fields2,
1494
fields_list.elements, tmp_all_fields1))
1496
curr_join->tmp_fields_list2= tmp_fields_list2;
1497
curr_join->tmp_all_fields2= tmp_all_fields2;
1499
curr_fields_list= &curr_join->tmp_fields_list2;
1500
curr_all_fields= &curr_join->tmp_all_fields2;
1501
curr_join->set_items_ref_array(items2);
1502
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
1503
curr_join->tmp_table_param.sum_func_count= 0;
1505
if (curr_tmp_table->distinct)
1506
curr_join->select_distinct=0; /* Each row is unique */
1508
curr_join->join_free(); /* Free quick selects */
1509
if (curr_join->select_distinct && ! curr_join->group_list)
1511
session->set_proc_info("Removing duplicates");
1512
if (curr_join->tmp_having)
1513
curr_join->tmp_having->update_used_tables();
1515
if (remove_duplicates(curr_join, curr_tmp_table,
1516
*curr_fields_list, curr_join->tmp_having))
1519
curr_join->tmp_having=0;
1520
curr_join->select_distinct=0;
1522
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
1523
if (make_simple_join(curr_join, curr_tmp_table))
1525
calc_group_buffer(curr_join, curr_join->group_list);
1526
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
1530
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
1532
if (make_group_fields(this, curr_join))
1538
init_items_ref_array();
1539
items3= ref_pointer_array + (all_fields.elements*4);
1540
setup_copy_fields(session, &curr_join->tmp_table_param,
1541
items3, tmp_fields_list3, tmp_all_fields3,
1542
curr_fields_list->elements, *curr_all_fields);
1543
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
1544
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
1545
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
1546
curr_join->tmp_all_fields3= tmp_all_fields3;
1547
curr_join->tmp_fields_list3= tmp_fields_list3;
1551
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
1552
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
1553
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
1555
curr_fields_list= &tmp_fields_list3;
1556
curr_all_fields= &tmp_all_fields3;
1557
curr_join->set_items_ref_array(items3);
1559
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1561
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
1562
session->is_fatal_error)
1565
if (curr_join->group_list || curr_join->order)
1567
session->set_proc_info("Sorting result");
1568
/* If we have already done the group, add HAVING to sorted table */
1569
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
1571
// Some tables may have been const
1572
curr_join->tmp_having->update_used_tables();
1573
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];
1574
table_map used_tables= (curr_join->const_table_map |
1575
curr_table->table->map);
1577
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
1578
if (sort_table_cond)
1580
if (!curr_table->select)
1581
if (!(curr_table->select= new optimizer::SqlSelect))
1583
if (!curr_table->select->cond)
1584
curr_table->select->cond= sort_table_cond;
1585
else // This should never happen
1587
if (!(curr_table->select->cond=
1588
new Item_cond_and(curr_table->select->cond,
1592
Item_cond_and do not need fix_fields for execution, its parameters
1593
are fixed or do not need fix_fields, too
1595
curr_table->select->cond->quick_fix_field();
1597
curr_table->select_cond= curr_table->select->cond;
1598
curr_table->select_cond->top_level_item();
1599
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
1606
curr_join->select_limit= HA_POS_ERROR;
1610
We can abort sorting after session->select_limit rows if we there is no
1611
WHERE clause for any tables after the sorted one.
1613
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
1614
JoinTable *end_table= &curr_join->join_tab[curr_join->tables];
1615
for (; curr_table < end_table ; curr_table++)
1618
table->keyuse is set in the case there was an original WHERE clause
1619
on the table that was optimized away.
1621
if (curr_table->select_cond ||
1622
(curr_table->keyuse && !curr_table->first_inner))
1624
/* We have to sort all rows */
1625
curr_join->select_limit= HA_POS_ERROR;
1630
if (curr_join->join_tab == join_tab && save_join_tab())
1633
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
1634
chose FILESORT to be faster than INDEX SCAN or there is no
1635
suitable index present.
1636
Note, that create_sort_index calls test_if_skip_sort_order and may
1637
finally replace sorting with index scan if there is a LIMIT clause in
1638
the query. XXX: it's never shown in EXPLAIN!
1639
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
1641
if (create_sort_index(session, curr_join,
1642
curr_join->group_list ?
1643
curr_join->group_list : curr_join->order,
1644
curr_join->select_limit,
1645
(select_options & OPTION_FOUND_ROWS ?
1646
HA_POS_ERROR : unit->select_limit_cnt),
1647
curr_join->group_list ? true : false))
1650
sortorder= curr_join->sortorder;
1651
if (curr_join->const_tables != curr_join->tables &&
1652
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
1655
If no IO cache exists for the first table then we are using an
1656
INDEX SCAN and no filesort. Thus we should not remove the sorted
1657
attribute on the INDEX SCAN.
1663
/* XXX: When can we have here session->is_error() not zero? */
1664
if (session->is_error())
1666
error= session->is_error();
1669
curr_join->having= curr_join->tmp_having;
1670
curr_join->fields= curr_fields_list;
1672
session->set_proc_info("Sending data");
1673
result->send_fields(*curr_fields_list);
1674
error= do_select(curr_join, curr_fields_list, NULL);
1675
session->limit_found_rows= curr_join->send_records;
1677
/* Accumulate the counts from all join iterations of all join parts. */
1678
session->examined_row_count+= curr_join->examined_rows;
1681
With EXPLAIN EXTENDED we have to restore original ref_array
1682
for a derived table which is always materialized.
1683
Otherwise we would not be able to print the query correctly.
1685
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
1686
set_items_ref_array(items0);
1695
Return error that hold JOIN.
1699
select_lex->join= 0;
1703
if (join_tab != tmp_join->join_tab)
1705
JoinTable *tab, *end;
1706
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
1709
tmp_join->tmp_join= 0;
1710
tmp_table_param.copy_field=0;
1711
return(tmp_join->destroy());
1716
if (exec_tmp_table1)
1717
exec_tmp_table1->free_tmp_table(session);
1718
if (exec_tmp_table2)
1719
exec_tmp_table2->free_tmp_table(session);
1721
delete_dynamic(&keyuse);
1726
Setup for execution all subqueries of a query, for which the optimizer
1727
chose hash semi-join.
1729
@details Iterate over all subqueries of the query, and if they are under an
1730
IN predicate, and the optimizer chose to compute it via hash semi-join:
1731
- try to initialize all data structures needed for the materialized execution
1732
of the IN predicate,
1733
- if this fails, then perform the IN=>EXISTS transformation which was
1734
previously blocked during JOIN::prepare.
1736
This method is part of the "code generation" query processing phase.
1738
This phase must be called after substitute_for_best_equal_field() because
1739
that function may replace items with other items from a multiple equality,
1740
and we need to reference the correct items in the index access method of the
1743
@return Operation status
1744
@retval false success.
1745
@retval true error occurred.
1747
bool JOIN::setup_subquery_materialization()
1749
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1750
un= un->next_unit())
1752
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
1754
Item_subselect *subquery_predicate= sl->master_unit()->item;
1755
if (subquery_predicate &&
1756
subquery_predicate->substype() == Item_subselect::IN_SUBS)
1758
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
1759
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
1760
in_subs->setup_engine())
1769
Partially cleanup JOIN after it has executed: close index or rnd read
1770
(table cursors), free quick selects.
1772
This function is called in the end of execution of a JOIN, before the used
1773
tables are unlocked and closed.
1775
For a join that is resolved using a temporary table, the first sweep is
1776
performed against actual tables and an intermediate result is inserted
1777
into the temprorary table.
1778
The last sweep is performed against the temporary table. Therefore,
1779
the base tables and associated buffers used to fill the temporary table
1780
are no longer needed, and this function is called to free them.
1782
For a join that is performed without a temporary table, this function
1783
is called after all rows are sent, but before EOF packet is sent.
1785
For a simple SELECT with no subqueries this function performs a full
1786
cleanup of the JOIN and calls mysql_unlock_read_tables to free used base
1789
If a JOIN is executed for a subquery or if it has a subquery, we can't
1790
do the full cleanup and need to do a partial cleanup only.
1791
- If a JOIN is not the top level join, we must not unlock the tables
1792
because the outer select may not have been evaluated yet, and we
1793
can't unlock only selected tables of a query.
1794
- Additionally, if this JOIN corresponds to a correlated subquery, we
1795
should not free quick selects and join buffers because they will be
1796
needed for the next execution of the correlated subquery.
1797
- However, if this is a JOIN for a [sub]select, which is not
1798
a correlated subquery itself, but has subqueries, we can free it
1799
fully and also free JOINs of all its subqueries. The exception
1800
is a subquery in SELECT list, e.g: @n
1801
SELECT a, (select cmax(b) from t1) group by c @n
1802
This subquery will not be evaluated at first sweep and its value will
1803
not be inserted into the temporary table. Instead, it's evaluated
1804
when selecting from the temporary table. Therefore, it can't be freed
1805
here even though it's not correlated.
1808
Unlock tables even if the join isn't top level select in the tree
1810
void JOIN::join_free()
1812
Select_Lex_Unit *tmp_unit;
1815
Optimization: if not EXPLAIN and we are done with the JOIN,
1818
bool full= (!select_lex->uncacheable && !session->lex->describe);
1819
bool can_unlock= full;
1823
for (tmp_unit= select_lex->first_inner_unit();
1825
tmp_unit= tmp_unit->next_unit())
1826
for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
1828
Item_subselect *subselect= sl->master_unit()->item;
1829
bool full_local= full && (!subselect || subselect->is_evaluated());
1831
If this join is evaluated, we can fully clean it up and clean up all
1832
its underlying joins even if they are correlated -- they will not be
1833
used any more anyway.
1834
If this join is not yet evaluated, we still must clean it up to
1835
close its table cursors -- it may never get evaluated, as in case of
1836
... HAVING false OR a IN (SELECT ...))
1837
but all table cursors must be closed before the unlock.
1839
sl->cleanup_all_joins(full_local);
1840
/* Can't unlock if at least one JOIN is still needed */
1841
can_unlock= can_unlock && full_local;
1845
We are not using tables anymore
1846
Unlock all tables. We may be in an INSERT .... SELECT statement.
1848
if (can_unlock && lock && session->lock &&
1849
!(select_options & SELECT_NO_UNLOCK) &&
1850
!select_lex->subquery_in_having &&
1851
(select_lex == (session->lex->unit.fake_select_lex ?
1852
session->lex->unit.fake_select_lex : &session->lex->select_lex)))
1855
TODO: unlock tables even if the join isn't top level select in the
1858
mysql_unlock_read_tables(session, lock); // Don't free join->lock
1867
Free resources of given join.
1869
@param fill true if we should free all resources, call with full==1
1870
should be last, before it this function can be called with
1874
With subquery this function definitely will be called several times,
1875
but even for simple query it can be called several times.
1877
void JOIN::cleanup(bool full)
1881
JoinTable *tab,*end;
1883
Only a sorted table may be cached. This sorted table is always the
1884
first non const table in join->table
1886
if (tables > const_tables) // Test for not-const tables
1888
table[const_tables]->free_io_cache();
1889
table[const_tables]->filesort_free_buffers(full);
1894
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1900
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1903
tab->table->cursor->ha_index_or_rnd_end();
1908
We are not using tables anymore
1909
Unlock all tables. We may be in an INSERT .... SELECT statement.
1914
tmp_table_param.copy_field= 0;
1915
group_fields.delete_elements();
1917
We can't call delete_elements() on copy_funcs as this will cause
1918
problems in free_elements() as some of the elements are then deleted.
1920
tmp_table_param.copy_funcs.empty();
1922
If we have tmp_join and 'this' JOIN is not tmp_join and
1923
tmp_table_param.copy_field's of them are equal then we have to remove
1924
pointer to tmp_table_param.copy_field from tmp_join, because it qill
1925
be removed in tmp_table_param.cleanup().
1929
tmp_join->tmp_table_param.copy_field ==
1930
tmp_table_param.copy_field)
1932
tmp_join->tmp_table_param.copy_field=
1933
tmp_join->tmp_table_param.save_copy_field= 0;
1935
tmp_table_param.cleanup();
1941
used only in JOIN::clear
1943
static void clear_tables(JOIN *join)
1946
must clear only the non-const tables, as const tables
1947
are not re-calculated.
1949
for (uint32_t i= join->const_tables; i < join->tables; i++)
1950
join->table[i]->mark_as_null_row(); // All fields are NULL
1954
Make an array of pointers to sum_functions to speed up
1955
sum_func calculation.
1962
bool JOIN::alloc_func_list()
1964
uint32_t func_count, group_parts;
1966
func_count= tmp_table_param.sum_func_count;
1968
If we are using rollup, we need a copy of the summary functions for
1971
if (rollup.state != ROLLUP::STATE_NONE)
1972
func_count*= (send_group_parts+1);
1974
group_parts= send_group_parts;
1976
If distinct, reserve memory for possible
1977
disctinct->group_by optimization
1979
if (select_distinct)
1981
group_parts+= fields_list.elements;
1983
If the order_st clause is specified then it's possible that
1984
it also will be optimized, so reserve space for it too
1989
for (ord= order; ord; ord= ord->next)
1994
/* This must use calloc() as rollup_make_fields depends on this */
1995
sum_funcs= (Item_sum**) session->calloc(sizeof(Item_sum**) * (func_count+1) +
1996
sizeof(Item_sum***) * (group_parts+1));
1997
sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
1998
return(sum_funcs == 0);
2002
Initialize 'sum_funcs' array with all Item_sum objects.
2004
@param field_list All items
2005
@param send_fields Items in select list
2006
@param before_group_by Set to 1 if this is called before GROUP BY handling
2007
@param recompute Set to true if sum_funcs must be recomputed
2014
bool JOIN::make_sum_func_list(List<Item> &field_list,
2015
List<Item> &send_fields,
2016
bool before_group_by,
2019
List_iterator_fast<Item> it(field_list);
2023
if (*sum_funcs && !recompute)
2024
return(false); /* We have already initialized sum_funcs. */
2029
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2030
(!((Item_sum*) item)->depended_from() ||
2031
((Item_sum *)item)->depended_from() == select_lex))
2032
*func++= (Item_sum*) item;
2034
if (before_group_by && rollup.state == ROLLUP::STATE_INITED)
2036
rollup.state= ROLLUP::STATE_READY;
2037
if (rollup_make_fields(field_list, send_fields, &func))
2038
return(true); // Should never happen
2040
else if (rollup.state == ROLLUP::STATE_NONE)
2042
for (uint32_t i=0 ; i <= send_group_parts ;i++)
2043
sum_funcs_end[i]= func;
2045
else if (rollup.state == ROLLUP::STATE_READY)
2046
return(false); // Don't put end marker
2047
*func=0; // End marker
2051
/** Allocate memory needed for other rollup functions. */
2052
bool JOIN::rollup_init()
2057
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2058
rollup.state= ROLLUP::STATE_INITED;
2061
Create pointers to the different sum function groups
2062
These are updated by rollup_make_fields()
2064
tmp_table_param.group_parts= send_group_parts;
2066
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
2068
sizeof(List<Item>) +
2069
ref_pointer_array_size)
2070
* send_group_parts )))
2073
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
2074
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
2075
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
2078
Prepare space for field list for the different levels
2079
These will be filled up in rollup_make_fields()
2081
for (i= 0 ; i < send_group_parts ; i++)
2083
rollup.null_items[i]= new (session->mem_root) Item_null_result();
2084
List<Item> *rollup_fields= &rollup.fields[i];
2085
rollup_fields->empty();
2086
rollup.ref_pointer_arrays[i]= ref_array;
2087
ref_array+= all_fields.elements;
2089
for (i= 0 ; i < send_group_parts; i++)
2091
for (j=0 ; j < fields_list.elements ; j++)
2092
rollup.fields[i].push_back(rollup.null_items[i]);
2094
List_iterator<Item> it(all_fields);
2096
while ((item= it++))
2098
order_st *group_tmp;
2099
bool found_in_group= 0;
2101
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2103
if (*group_tmp->item == item)
2105
item->maybe_null= 1;
2107
if (item->const_item())
2110
For ROLLUP queries each constant item referenced in GROUP BY list
2111
is wrapped up into an Item_func object yielding the same value
2112
as the constant item. The objects of the wrapper class are never
2113
considered as constant items and besides they inherit all
2114
properties of the Item_result_field class.
2115
This wrapping allows us to ensure writing constant items
2116
into temporary tables whenever the result of the ROLLUP
2117
operation has to be written into a temporary table, e.g. when
2118
ROLLUP is used together with DISTINCT in the SELECT list.
2119
Usually when creating temporary tables for a intermidiate
2120
result we do not include fields for constant expressions.
2122
Item* new_item= new Item_func_rollup_const(item);
2125
new_item->fix_fields(session, (Item **) 0);
2126
session->change_item_tree(it.ref(), new_item);
2127
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
2129
if (*tmp->item == item)
2130
session->change_item_tree(tmp->item, new_item);
2135
if (item->type() == Item::FUNC_ITEM && !found_in_group)
2137
bool changed= false;
2138
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
2141
We have to prevent creation of a field in a temporary table for
2142
an expression that contains GROUP BY attributes.
2143
Marking the expression item as 'with_sum_func' will ensure this.
2146
item->with_sum_func= 1;
2153
Fill up rollup structures with pointers to fields to use.
2155
Creates copies of item_sum items for each sum level.
2157
@param fields_arg List of all fields (hidden and real ones)
2158
@param sel_fields Pointer to selected fields
2159
@param func Store here a pointer to all fields
2163
In this case func is pointing to next not used element.
2167
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2169
List_iterator_fast<Item> it(fields_arg);
2170
Item *first_field= sel_fields.head();
2174
Create field lists for the different levels
2176
The idea here is to have a separate field list for each rollup level to
2177
avoid all runtime checks of which columns should be NULL.
2179
The list is stored in reverse order to get sum function in such an order
2180
in func that it makes it easy to reset them with init_sum_functions()
2182
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2184
rollup.fields[0] will contain list where a,b,c is NULL
2185
rollup.fields[1] will contain list where b,c is NULL
2187
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
2189
sum_funcs_end[0] points to all sum functions
2190
sum_funcs_end[1] points to all sum functions, except grand totals
2194
for (level=0 ; level < send_group_parts ; level++)
2197
uint32_t pos= send_group_parts - level -1;
2198
bool real_fields= 0;
2200
List_iterator<Item> new_it(rollup.fields[pos]);
2201
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
2202
order_st *start_group;
2204
/* Point to first hidden field */
2205
Item **ref_array= ref_array_start + fields_arg.elements-1;
2207
/* Remember where the sum functions ends for the previous level */
2208
sum_funcs_end[pos+1]= *func;
2210
/* Find the start of the group for this level */
2211
for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
2215
while ((item= it++))
2217
if (item == first_field)
2219
real_fields= 1; // End of hidden fields
2220
ref_array= ref_array_start;
2223
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2224
(!((Item_sum*) item)->depended_from() ||
2225
((Item_sum *)item)->depended_from() == select_lex))
2229
This is a top level summary function that must be replaced with
2230
a sum function that is reset for this level.
2232
NOTE: This code creates an object which is not that nice in a
2233
sub select. Fortunately it's not common to have rollup in
2236
item= item->copy_or_same(session);
2237
((Item_sum*) item)->make_unique();
2238
*(*func)= (Item_sum*) item;
2243
/* Check if this is something that is part of this group by */
2244
order_st *group_tmp;
2245
for (group_tmp= start_group, i= pos ;
2246
group_tmp ; group_tmp= group_tmp->next, i++)
2248
if (*group_tmp->item == item)
2251
This is an element that is used by the GROUP BY and should be
2252
set to NULL in this level
2254
Item_null_result *null_item= new (session->mem_root) Item_null_result();
2257
item->maybe_null= 1; // Value will be null sometimes
2258
null_item->result_field= item->get_tmp_table_field();
2267
(void) new_it++; // Point to next item
2268
new_it.replace(item); // Replace previous
2275
sum_funcs_end[0]= *func; // Point to last function
2280
Send all rollup levels higher than the current one to the client.
2284
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2287
@param idx Level we are on:
2288
- 0 = Total sum level
2289
- 1 = First group changed (a)
2290
- 2 = Second group changed (a,b)
2295
1 If send_data_failed()
2297
int JOIN::rollup_send_data(uint32_t idx)
2300
for (i= send_group_parts ; i-- > idx ; )
2302
/* Get reference pointers to sum functions in place */
2303
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2304
ref_pointer_array_size);
2305
if ((!having || having->val_int()))
2307
if (send_records < unit->select_limit_cnt && do_send_rows &&
2308
result->send_data(rollup.fields[i]))
2313
/* Restore ref_pointer_array */
2314
set_items_ref_array(current_ref_pointer_array);
2319
Write all rollup levels higher than the current one to a temp table.
2323
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
2326
@param idx Level we are on:
2327
- 0 = Total sum level
2328
- 1 = First group changed (a)
2329
- 2 = Second group changed (a,b)
2330
@param table reference to temp table
2335
1 if write_data_failed()
2337
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
2340
for (i= send_group_parts ; i-- > idx ; )
2342
/* Get reference pointers to sum functions in place */
2343
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2344
ref_pointer_array_size);
2345
if ((!having || having->val_int()))
2349
List_iterator_fast<Item> it(rollup.fields[i]);
2350
while ((item= it++))
2352
if (item->type() == Item::NULL_ITEM && item->is_result_field())
2353
item->save_in_result_field(1);
2355
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2356
if ((write_error= table_arg->cursor->ha_write_row(table_arg->record[0])))
2358
if (create_myisam_from_heap(session, table_arg,
2359
tmp_table_param.start_recinfo,
2360
&tmp_table_param.recinfo,
2366
/* Restore ref_pointer_array */
2367
set_items_ref_array(current_ref_pointer_array);
2372
clear results if there are not rows found for group
2373
(end_send_group/end_write_group)
2378
copy_fields(&tmp_table_param);
2382
Item_sum *func, **func_ptr= sum_funcs;
2383
while ((func= *(func_ptr++)))
2389
change select_result object of JOIN.
2391
@param res new select_result object
2398
bool JOIN::change_result(select_result *res)
2401
if (result->prepare(fields_list, select_lex->master_unit()))
2409
Cache constant expressions in WHERE, HAVING, ON conditions.
2412
void JOIN::cache_const_exprs()
2414
bool cache_flag= false;
2415
bool *analyzer_arg= &cache_flag;
2417
/* No need in cache if all tables are constant. */
2418
if (const_tables == tables)
2422
conds->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2423
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2426
having->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2427
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2429
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
2431
if (*tab->on_expr_ref)
2434
(*tab->on_expr_ref)->compile(&Item::cache_const_expr_analyzer,
2435
(unsigned char **)&analyzer_arg,
2436
&Item::cache_const_expr_transformer,
2437
(unsigned char *)&cache_flag);
2445
Process one record of the nested loop join.
2449
This function will evaluate parts of WHERE/ON clauses that are
2450
applicable to the partial record on hand and in case of success
2451
submit this record to the next level of the nested loop.
2453
enum_nested_loop_state evaluate_join_record(JOIN *join, JoinTable *join_tab, int error)
2455
bool not_used_in_distinct= join_tab->not_used_in_distinct;
2456
ha_rows found_records= join->found_records;
2457
COND *select_cond= join_tab->select_cond;
2459
if (error > 0 || (join->session->is_error())) // Fatal error
2460
return NESTED_LOOP_ERROR;
2462
return NESTED_LOOP_NO_MORE_ROWS;
2463
if (join->session->killed) // Aborted by user
2465
join->session->send_kill_message();
2466
return NESTED_LOOP_KILLED;
2468
if (!select_cond || select_cond->val_int())
2471
There is no select condition or the attached pushed down
2472
condition is true => a match is found.
2475
while (join_tab->first_unmatched && found)
2478
The while condition is always false if join_tab is not
2479
the last inner join table of an outer join operation.
2481
JoinTable *first_unmatched= join_tab->first_unmatched;
2483
Mark that a match for current outer table is found.
2484
This activates push down conditional predicates attached
2485
to the all inner tables of the outer join.
2487
first_unmatched->found= 1;
2488
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2490
if (tab->table->reginfo.not_exists_optimize)
2491
return NESTED_LOOP_NO_MORE_ROWS;
2492
/* Check all predicates that has just been activated. */
2494
Actually all predicates non-guarded by first_unmatched->found
2495
will be re-evaluated again. It could be fixed, but, probably,
2496
it's not worth doing now.
2498
if (tab->select_cond && !tab->select_cond->val_int())
2500
/* The condition attached to table tab is false */
2501
if (tab == join_tab)
2506
Set a return point if rejected predicate is attached
2507
not to the last table of the current nest level.
2509
join->return_tab= tab;
2510
return NESTED_LOOP_OK;
2515
Check whether join_tab is not the last inner table
2516
for another embedding outer join.
2518
if ((first_unmatched= first_unmatched->first_upper) &&
2519
first_unmatched->last_inner != join_tab)
2521
join_tab->first_unmatched= first_unmatched;
2524
JoinTable *return_tab= join->return_tab;
2525
join_tab->found_match= true;
2528
It was not just a return to lower loop level when one
2529
of the newly activated predicates is evaluated as false
2530
(See above join->return_tab= tab).
2532
join->examined_rows++;
2533
join->session->row_count++;
2537
enum enum_nested_loop_state rc;
2538
/* A match from join_tab is found for the current partial join. */
2539
rc= (*join_tab->next_select)(join, join_tab+1, 0);
2540
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2542
if (return_tab < join->return_tab)
2543
join->return_tab= return_tab;
2545
if (join->return_tab < join_tab)
2546
return NESTED_LOOP_OK;
2548
Test if this was a SELECT DISTINCT query on a table that
2549
was not in the field list; In this case we can abort if
2550
we found a row, as no new rows can be added to the result.
2552
if (not_used_in_distinct && found_records != join->found_records)
2553
return NESTED_LOOP_NO_MORE_ROWS;
2556
join_tab->read_record.cursor->unlock_row();
2561
The condition pushed down to the table join_tab rejects all rows
2562
with the beginning coinciding with the current partial join.
2564
join->examined_rows++;
2565
join->session->row_count++;
2566
join_tab->read_record.cursor->unlock_row();
2568
return NESTED_LOOP_OK;
2573
Construct a NULL complimented partial join record and feed it to the next
2574
level of the nested loop. This function is used in case we have
2575
an OUTER join and no matching record was found.
2577
enum_nested_loop_state evaluate_null_complemented_join_record(JOIN *join, JoinTable *join_tab)
2580
The table join_tab is the first inner table of a outer join operation
2581
and no matches has been found for the current outer row.
2583
JoinTable *last_inner_tab= join_tab->last_inner;
2584
/* Cache variables for faster loop */
2586
for ( ; join_tab <= last_inner_tab ; join_tab++)
2588
/* Change the the values of guard predicate variables. */
2590
join_tab->not_null_compl= 0;
2591
/* The outer row is complemented by nulls for each inner tables */
2592
join_tab->table->restoreRecordAsDefault(); // Make empty record
2593
join_tab->table->mark_as_null_row(); // For group by without error
2594
select_cond= join_tab->select_cond;
2595
/* Check all attached conditions for inner table rows. */
2596
if (select_cond && !select_cond->val_int())
2597
return NESTED_LOOP_OK;
2601
The row complemented by nulls might be the first row
2602
of embedding outer joins.
2603
If so, perform the same actions as in the code
2604
for the first regular outer join row above.
2608
JoinTable *first_unmatched= join_tab->first_unmatched;
2609
if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
2611
join_tab->first_unmatched= first_unmatched;
2612
if (! first_unmatched)
2614
first_unmatched->found= 1;
2615
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2617
if (tab->select_cond && !tab->select_cond->val_int())
2619
join->return_tab= tab;
2620
return NESTED_LOOP_OK;
2625
The row complemented by nulls satisfies all conditions
2626
attached to inner tables.
2627
Send the row complemented by nulls to be joined with the
2630
return (*join_tab->next_select)(join, join_tab+1, 0);
2633
enum_nested_loop_state flush_cached_records(JOIN *join, JoinTable *join_tab, bool skip_last)
2635
enum_nested_loop_state rc= NESTED_LOOP_OK;
2639
join_tab->table->null_row= 0;
2640
if (!join_tab->cache.records)
2641
return NESTED_LOOP_OK; /* Nothing to do */
2643
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
2644
if (join_tab->use_quick == 2)
2646
if (join_tab->select->quick)
2647
{ /* Used quick select last. reset it */
2648
delete join_tab->select->quick;
2649
join_tab->select->quick=0;
2652
/* read through all records */
2653
if ((error=join_init_read_record(join_tab)))
2655
reset_cache_write(&join_tab->cache);
2656
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2659
for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)
2661
tmp->status=tmp->table->status;
2662
tmp->table->status=0;
2665
info= &join_tab->read_record;
2668
if (join->session->killed)
2670
join->session->send_kill_message();
2671
return NESTED_LOOP_KILLED;
2673
optimizer::SqlSelect *select= join_tab->select;
2674
if (rc == NESTED_LOOP_OK &&
2675
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2678
reset_cache_read(&join_tab->cache);
2679
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2681
join_tab->readCachedRecord();
2682
if (!select || !select->skip_record())
2686
rc= (join_tab->next_select)(join,join_tab+1,0);
2687
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2689
reset_cache_write(&join_tab->cache);
2694
return NESTED_LOOP_ERROR;
2698
} while (!(error=info->read_record(info)));
2701
join_tab->readCachedRecord(); // Restore current record
2702
reset_cache_write(&join_tab->cache);
2703
if (error > 0) // Fatal error
2704
return NESTED_LOOP_ERROR;
2705
for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2706
tmp2->table->status=tmp2->status;
2707
return NESTED_LOOP_OK;
2710
/*****************************************************************************
2712
Functions that end one nested loop iteration. Different functions
2713
are used to support GROUP BY clause and to redirect records
2714
to a table (e.g. in case of SELECT into a temporary table) or to the
2718
NESTED_LOOP_OK - the record has been successfully handled
2719
NESTED_LOOP_ERROR - a fatal error (like table corruption)
2721
NESTED_LOOP_KILLED - thread shutdown was requested while processing
2723
NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;
2724
additionally, the nested loop produced the
2725
number of rows specified in the LIMIT clause
2727
NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
2728
additionally, there is a cursor and the nested
2729
loop algorithm produced the number of rows
2730
that is specified for current cursor fetch
2732
All return values except NESTED_LOOP_OK abort the nested loop.
2733
*****************************************************************************/
2734
enum_nested_loop_state end_send(JOIN *join, JoinTable *, bool end_of_records)
2736
if (! end_of_records)
2739
if (join->having && join->having->val_int() == 0)
2740
return NESTED_LOOP_OK; // Didn't match having
2742
if (join->do_send_rows)
2743
error=join->result->send_data(*join->fields);
2745
return NESTED_LOOP_ERROR;
2746
if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2748
if (join->select_options & OPTION_FOUND_ROWS)
2750
JoinTable *jt=join->join_tab;
2751
if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2752
&& !join->send_group_parts && !join->having && !jt->select_cond &&
2753
!(jt->select && jt->select->quick) &&
2754
(jt->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
2757
/* Join over all rows in table; Return number of found rows */
2758
Table *table= jt->table;
2760
join->select_options^= OPTION_FOUND_ROWS;
2761
if (table->sort.record_pointers ||
2762
(table->sort.io_cache && my_b_inited(table->sort.io_cache)))
2764
/* Using filesort */
2765
join->send_records= table->sort.found_records;
2769
table->cursor->info(HA_STATUS_VARIABLE);
2770
join->send_records= table->cursor->stats.records;
2775
join->do_send_rows= 0;
2776
if (join->unit->fake_select_lex)
2777
join->unit->fake_select_lex->select_limit= 0;
2778
return NESTED_LOOP_OK;
2781
return NESTED_LOOP_QUERY_LIMIT; // Abort nicely
2783
else if (join->send_records >= join->fetch_limit)
2786
There is a server side cursor and all rows for
2787
this fetch request are sent.
2789
return NESTED_LOOP_CURSOR_LIMIT;
2793
return NESTED_LOOP_OK;
2796
enum_nested_loop_state end_write(JOIN *join, JoinTable *, bool end_of_records)
2798
Table *table= join->tmp_table;
2800
if (join->session->killed) // Aborted by user
2802
join->session->send_kill_message();
2803
return NESTED_LOOP_KILLED;
2805
if (!end_of_records)
2807
copy_fields(&join->tmp_table_param);
2808
copy_funcs(join->tmp_table_param.items_to_copy);
2809
if (!join->having || join->having->val_int())
2812
join->found_records++;
2813
if ((error=table->cursor->ha_write_row(table->record[0])))
2815
if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))
2817
if (create_myisam_from_heap(join->session, table,
2818
join->tmp_table_param.start_recinfo,
2819
&join->tmp_table_param.recinfo,
2821
return NESTED_LOOP_ERROR; // Not a table_is_full error
2822
table->s->uniques= 0; // To ensure rows are the same
2824
if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
2826
if (!(join->select_options & OPTION_FOUND_ROWS))
2827
return NESTED_LOOP_QUERY_LIMIT;
2828
join->do_send_rows= 0;
2829
join->unit->select_limit_cnt= HA_POS_ERROR;
2830
return NESTED_LOOP_OK;
2835
return NESTED_LOOP_OK;
2838
/** Group by searching after group record and updating it if possible. */
2839
enum_nested_loop_state end_update(JOIN *join, JoinTable *, bool end_of_records)
2841
Table *table= join->tmp_table;
2846
return NESTED_LOOP_OK;
2847
if (join->session->killed) // Aborted by user
2849
join->session->send_kill_message();
2850
return NESTED_LOOP_KILLED;
2853
join->found_records++;
2854
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2855
/* Make a key of group index */
2856
for (group=table->group ; group ; group=group->next)
2858
Item *item= *group->item;
2859
item->save_org_in_field(group->field);
2860
/* Store in the used key if the field was 0 */
2861
if (item->maybe_null)
2862
group->buff[-1]= (char) group->field->is_null();
2864
if (!table->cursor->index_read_map(table->record[1],
2865
join->tmp_table_param.group_buff,
2868
{ /* Update old record */
2869
table->restoreRecord();
2870
update_tmptable_sum_func(join->sum_funcs,table);
2871
if ((error= table->cursor->ha_update_row(table->record[1],
2874
table->print_error(error,MYF(0));
2875
return NESTED_LOOP_ERROR;
2877
return NESTED_LOOP_OK;
2881
Copy null bits from group key to table
2882
We can't copy all data as the key may have different format
2883
as the row data (for example as with VARCHAR keys)
2885
KEY_PART_INFO *key_part;
2886
for (group=table->group,key_part=table->key_info[0].key_part;
2888
group=group->next,key_part++)
2890
if (key_part->null_bit)
2891
memcpy(table->record[0]+key_part->offset, group->buff, 1);
2893
init_tmptable_sum_functions(join->sum_funcs);
2894
copy_funcs(join->tmp_table_param.items_to_copy);
2895
if ((error=table->cursor->ha_write_row(table->record[0])))
2897
if (create_myisam_from_heap(join->session, table,
2898
join->tmp_table_param.start_recinfo,
2899
&join->tmp_table_param.recinfo,
2901
return NESTED_LOOP_ERROR; // Not a table_is_full error
2902
/* Change method to update rows */
2903
table->cursor->ha_index_init(0, 0);
2904
join->join_tab[join->tables-1].next_select= end_unique_update;
2906
join->send_records++;
2907
return NESTED_LOOP_OK;
2910
/** Like end_update, but this is done with unique constraints instead of keys. */
2911
enum_nested_loop_state end_unique_update(JOIN *join, JoinTable *, bool end_of_records)
2913
Table *table= join->tmp_table;
2917
return NESTED_LOOP_OK;
2918
if (join->session->killed) // Aborted by user
2920
join->session->send_kill_message();
2921
return NESTED_LOOP_KILLED;
2924
init_tmptable_sum_functions(join->sum_funcs);
2925
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2926
copy_funcs(join->tmp_table_param.items_to_copy);
2928
if (!(error= table->cursor->ha_write_row(table->record[0])))
2929
join->send_records++; // New group
2932
if ((int) table->get_dup_key(error) < 0)
2934
table->print_error(error,MYF(0));
2935
return NESTED_LOOP_ERROR;
2937
if (table->cursor->rnd_pos(table->record[1],table->cursor->dup_ref))
2939
table->print_error(error,MYF(0));
2940
return NESTED_LOOP_ERROR;
2942
table->restoreRecord();
2943
update_tmptable_sum_func(join->sum_funcs,table);
2944
if ((error= table->cursor->ha_update_row(table->record[1],
2947
table->print_error(error,MYF(0));
2948
return NESTED_LOOP_ERROR;
2951
return NESTED_LOOP_OK;
2955
allocate group fields or take prepared (cached).
2957
@param main_join join of current select
2958
@param curr_join current join (join of current select or temporary copy
2966
static bool make_group_fields(JOIN *main_join, JOIN *curr_join)
2968
if (main_join->group_fields_cache.elements)
2970
curr_join->group_fields= main_join->group_fields_cache;
2971
curr_join->sort_and_group= 1;
2975
if (alloc_group_fields(curr_join, curr_join->group_list))
2977
main_join->group_fields_cache= curr_join->group_fields;
2983
calc how big buffer we need for comparing group entries.
2985
static void calc_group_buffer(JOIN *join,order_st *group)
2987
uint32_t key_length=0, parts=0, null_parts=0;
2991
for (; group ; group=group->next)
2993
Item *group_item= *group->item;
2994
Field *field= group_item->get_tmp_table_field();
2997
enum_field_types type;
2998
if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
2999
key_length+=MAX_BLOB_WIDTH; // Can't be used as a key
3000
else if (type == DRIZZLE_TYPE_VARCHAR)
3001
key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
3003
key_length+= field->pack_length();
3007
switch (group_item->result_type()) {
3009
key_length+= sizeof(double);
3012
key_length+= sizeof(int64_t);
3014
case DECIMAL_RESULT:
3015
key_length+= my_decimal_get_binary_size(group_item->max_length -
3016
(group_item->decimals ? 1 : 0),
3017
group_item->decimals);
3021
enum enum_field_types type= group_item->field_type();
3023
As items represented as DATE/TIME fields in the group buffer
3024
have STRING_RESULT result type, we increase the length
3025
by 8 as maximum pack length of such fields.
3027
if (type == DRIZZLE_TYPE_DATE ||
3028
type == DRIZZLE_TYPE_DATETIME ||
3029
type == DRIZZLE_TYPE_TIMESTAMP)
3036
Group strings are taken as varstrings and require an length field.
3037
A field is not yet created by create_tmp_field()
3038
and the sizes should match up.
3040
key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3045
/* This case should never be choosen */
3047
my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
3051
if (group_item->maybe_null)
3054
join->tmp_table_param.group_length=key_length+null_parts;
3055
join->tmp_table_param.group_parts=parts;
3056
join->tmp_table_param.group_null_parts=null_parts;
3060
Get a list of buffers for saveing last group.
3062
Groups are saved in reverse order for easyer check loop.
3064
static bool alloc_group_fields(JOIN *join,order_st *group)
3068
for (; group ; group=group->next)
3070
Cached_item *tmp= new_Cached_item(join->session, *group->item);
3071
if (!tmp || join->group_fields.push_front(tmp))
3075
join->sort_and_group=1; /* Mark for do_select */
3079
static uint32_t cache_record_length(JOIN *join,uint32_t idx)
3082
JoinTable **pos,**end;
3083
Session *session=join->session;
3085
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
3089
JoinTable *join_tab= *pos;
3090
if (!join_tab->used_fieldlength) /* Not calced yet */
3091
calc_used_field_length(session, join_tab);
3092
length+=join_tab->used_fieldlength;
3098
Get the number of different row combinations for subset of partial join
3102
join The join structure
3103
idx Number of tables in the partial join order (i.e. the
3104
partial join order is in join->positions[0..idx-1])
3105
found_ref Bitmap of tables for which we need to find # of distinct
3109
Given a partial join order (in join->positions[0..idx-1]) and a subset of
3110
tables within that join order (specified in found_ref), find out how many
3111
distinct row combinations of subset tables will be in the result of the
3114
This is used as follows: Suppose we have a table accessed with a ref-based
3115
method. The ref access depends on current rows of tables in found_ref.
3116
We want to count # of different ref accesses. We assume two ref accesses
3117
will be different if at least one of access parameters is different.
3118
Example: consider a query
3120
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
3123
t1, ref access on t1.key=c1
3124
t2, ref access on t2.key=c2
3125
t3, ref access on t3.key=t1.field
3127
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
3128
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
3129
For t3: n_ref_scans = records_read(t1)*records_read(t2)
3130
n_distinct_ref_scans = #records_read(t1)
3132
The reason for having this function (at least the latest version of it)
3133
is that we need to account for buffering in join execution.
3135
An edge-case example: if we have a non-first table in join accessed via
3136
ref(const) or ref(param) where there is a small number of different
3137
values of param, then the access will likely hit the disk cache and will
3138
not require any disk seeks.
3140
The proper solution would be to assume an LRU disk cache of some size,
3141
calculate probability of cache hits, etc. For now we just count
3142
identical ref accesses as one.
3145
Expected number of row combinations
3147
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
3150
optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3151
for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1);
3155
if (pos->examinePosition(found_ref))
3157
found_ref|= pos->getRefDependMap();
3159
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
3160
with no matching row we will get position[t2].records_read==0.
3161
Actually the size of output is one null-complemented row, therefore
3162
we will use value of 1 whenever we get records_read==0.
3165
- the above case can't occur if inner part of outer join has more
3166
than one table: table with no matches will not be marked as const.
3168
- Ideally we should add 1 to records_read for every possible null-
3169
complemented row. We're not doing it because: 1. it will require
3170
non-trivial code and add overhead. 2. The value of records_read
3171
is an inprecise estimate and adding 1 (or, in the worst case,
3172
#max_nested_outer_joins=64-1) will not make it any more precise.
3174
if (pos->getFanout() > DBL_EPSILON)
3175
found*= pos->getFanout();
3182
Set up join struct according to best position.
3184
static bool get_best_combination(JOIN *join)
3187
table_map used_tables;
3188
JoinTable *join_tab,*j;
3189
optimizer::KeyUse *keyuse;
3190
uint32_t table_count;
3191
Session *session=join->session;
3192
optimizer::Position cur_pos;
3194
table_count=join->tables;
3195
if (!(join->join_tab=join_tab=
3196
(JoinTable*) session->alloc(sizeof(JoinTable)*table_count)))
3201
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
3202
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
3205
cur_pos= join->getPosFromOptimalPlan(tablenr);
3206
*j= *cur_pos.getJoinTable();
3207
form=join->table[tablenr]=j->table;
3208
used_tables|= form->map;
3209
form->reginfo.join_tab=j;
3210
if (!*j->on_expr_ref)
3211
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
3212
if (j->type == AM_CONST)
3213
continue; // Handled in make_join_stat..
3218
if (j->type == AM_SYSTEM)
3220
if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
3223
if (tablenr != join->const_tables)
3226
else if (create_ref_for_key(join, j, keyuse, used_tables))
3227
return(true); // Something went wrong
3230
for (i=0 ; i < table_count ; i++)
3231
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
3232
update_depend_map(join);
3236
/** Save const tables first as used tables. */
3237
static void set_position(JOIN *join,
3240
optimizer::KeyUse *key)
3242
optimizer::Position tmp_pos(1.0, /* This is a const table */
3247
join->setPosInPartialPlan(idx, tmp_pos);
3249
/* Move the const table as down as possible in best_ref */
3250
JoinTable **pos=join->best_ref+idx+1;
3251
JoinTable *next=join->best_ref[idx];
3252
for (;next != table ; pos++)
3254
JoinTable *tmp=pos[0];
3258
join->best_ref[idx]=table;
3262
Selects and invokes a search strategy for an optimal query plan.
3264
The function checks user-configurable parameters that control the search
3265
strategy for an optimal plan, selects the search method and then invokes
3266
it. Each specific optimization procedure stores the final optimal plan in
3267
the array 'join->best_positions', and the cost of the plan in
3270
@param join pointer to the structure providing all context info for
3272
@param join_tables set of the tables in the query
3279
static bool choose_plan(JOIN *join, table_map join_tables)
3281
uint32_t search_depth= join->session->variables.optimizer_search_depth;
3282
uint32_t prune_level= join->session->variables.optimizer_prune_level;
3283
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
3285
join->cur_embedding_map.reset();
3286
reset_nj_counters(join->join_list);
3288
if (SELECT_STRAIGHT_JOIN option is set)
3289
reorder tables so dependent tables come after tables they depend
3290
on, otherwise keep tables in the order they were specified in the query
3292
Apply heuristic: pre-sort all access plans with respect to the number of
3295
my_qsort(join->best_ref + join->const_tables,
3296
join->tables - join->const_tables, sizeof(JoinTable*),
3297
straight_join ? join_tab_cmp_straight : join_tab_cmp);
3300
optimize_straight_join(join, join_tables);
3304
if (search_depth == 0)
3305
/* Automatically determine a reasonable value for 'search_depth' */
3306
search_depth= determine_search_depth(join);
3307
if (greedy_search(join, join_tables, search_depth, prune_level))
3312
Store the cost of this query into a user variable
3313
Don't update last_query_cost for statements that are not "flat joins" :
3314
i.e. they have subqueries, unions or call stored procedures.
3315
TODO: calculate a correct cost for a query with subqueries and UNIONs.
3317
if (join->session->lex->is_single_level_stmt())
3318
join->session->status_var.last_query_cost= join->best_read;
3323
Find the best access path for an extension of a partial execution
3324
plan and add this path to the plan.
3326
The function finds the best access path to table 's' from the passed
3327
partial plan where an access path is the general term for any means to
3328
access the data in 's'. An access path may use either an index or a scan,
3329
whichever is cheaper. The input partial plan is passed via the array
3330
'join->positions' of length 'idx'. The chosen access method for 's' and its
3331
cost are stored in 'join->positions[idx]'.
3333
@param join pointer to the structure providing all context info
3335
@param s the table to be joined by the function
3336
@param session thread for the connection that submitted the query
3337
@param remaining_tables set of tables not included into the partial plan yet
3338
@param idx the length of the partial plan
3339
@param record_count estimate for the number of records returned by the
3341
@param read_time the cost of the partial plan
3346
static void best_access_path(JOIN *join,
3349
table_map remaining_tables,
3351
double record_count,
3354
optimizer::KeyUse *best_key= NULL;
3355
uint32_t best_max_key_part= 0;
3356
bool found_constraint= 0;
3357
double best= DBL_MAX;
3358
double best_time= DBL_MAX;
3359
double records= DBL_MAX;
3360
table_map best_ref_depends_map= 0;
3365
{ /* Use key if possible */
3366
Table *table= s->table;
3367
optimizer::KeyUse *keyuse= NULL;
3368
optimizer::KeyUse *start_key= NULL;
3369
double best_records= DBL_MAX;
3370
uint32_t max_key_part=0;
3372
/* Test how we can use keys */
3373
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
3374
for (keyuse= s->keyuse; keyuse->getTable() == table; )
3376
key_part_map found_part= 0;
3377
table_map found_ref= 0;
3378
uint32_t key= keyuse->getKey();
3379
KEY *keyinfo= table->key_info + key;
3380
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
3381
key_part_map const_part= 0;
3382
/* The or-null keypart in ref-or-null access: */
3383
key_part_map ref_or_null_part= 0;
3385
/* Calculate how many key segments of the current key we can use */
3388
do /* For each keypart */
3390
uint32_t keypart= keyuse->getKeypart();
3391
table_map best_part_found_ref= 0;
3392
double best_prev_record_reads= DBL_MAX;
3394
do /* For each way to access the keypart */
3398
if 1. expression doesn't refer to forward tables
3399
2. we won't get two ref-or-null's
3401
if (! (remaining_tables & keyuse->getUsedTables()) &&
3402
! (ref_or_null_part && (keyuse->getOptimizeFlags() &
3403
KEY_OPTIMIZE_REF_OR_NULL)))
3405
found_part|= keyuse->getKeypartMap();
3406
if (! (keyuse->getUsedTables() & ~join->const_table_map))
3407
const_part|= keyuse->getKeypartMap();
3409
double tmp2= prev_record_reads(join, idx, (found_ref |
3410
keyuse->getUsedTables()));
3411
if (tmp2 < best_prev_record_reads)
3413
best_part_found_ref= keyuse->getUsedTables() & ~join->const_table_map;
3414
best_prev_record_reads= tmp2;
3416
if (rec > keyuse->getTableRows())
3417
rec= keyuse->getTableRows();
3419
If there is one 'key_column IS NULL' expression, we can
3420
use this ref_or_null optimisation of this field
3422
if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)
3423
ref_or_null_part|= keyuse->getKeypartMap();
3427
} while (keyuse->getTable() == table && keyuse->getKey() == key &&
3428
keyuse->getKeypart() == keypart);
3429
found_ref|= best_part_found_ref;
3430
} while (keyuse->getTable() == table && keyuse->getKey() == key);
3433
Assume that that each key matches a proportional part of table.
3436
continue; // Nothing usable found
3438
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
3439
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
3442
found_constraint= 1;
3445
Check if we found full key
3447
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
3450
max_key_part= UINT32_MAX;
3451
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
3453
tmp = prev_record_reads(join, idx, found_ref);
3459
{ /* We found a const key */
3461
ReuseRangeEstimateForRef-1:
3462
We get here if we've found a ref(const) (c_i are constants):
3463
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
3465
If range optimizer was able to construct a "range"
3466
access on this index, then its condition "quick_cond" was
3467
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
3468
from the range optimizer.
3470
Proof of (*): By properties of range and ref optimizers
3471
quick_cond will be equal or tighther than ref_const_cond.
3472
ref_const_cond already covers "smallest" possible interval -
3473
a singlepoint interval over all keyparts. Therefore,
3474
quick_cond is equivalent to ref_const_cond (if it was an
3475
empty interval we wouldn't have got here).
3477
if (table->quick_keys.test(key))
3478
records= (double) table->quick_rows[key];
3481
/* quick_range couldn't use key! */
3482
records= (double) s->records/rec;
3487
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
3488
{ /* Prefer longer keys */
3490
((double) s->records / (double) rec *
3492
((double) (table->s->max_key_length-keyinfo->key_length) /
3493
(double) table->s->max_key_length)));
3495
records=2.0; /* Can't be as good as a unique */
3498
ReuseRangeEstimateForRef-2: We get here if we could not reuse
3499
E(#rows) from range optimizer. Make another try:
3501
If range optimizer produced E(#rows) for a prefix of the ref
3502
access we're considering, and that E(#rows) is lower then our
3503
current estimate, make an adjustment. The criteria of when we
3504
can make an adjustment is a special case of the criteria used
3505
in ReuseRangeEstimateForRef-3.
3507
if (table->quick_keys.test(key) &&
3508
const_part & (1 << table->quick_key_parts[key]) &&
3509
table->quick_n_ranges[key] == 1 &&
3510
records > (double) table->quick_rows[key])
3512
records= (double) table->quick_rows[key];
3515
/* Limit the number of matched rows */
3517
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3518
if (table->covering_keys.test(key))
3520
/* we can use only index tree */
3521
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3524
tmp= record_count * min(tmp,s->worst_seeks);
3530
Use as much key-parts as possible and a uniq key is better
3531
than a not unique key
3532
Set tmp to (previous record count) * (records / combination)
3534
if ((found_part & 1) &&
3535
(!(table->index_flags(key) & HA_ONLY_WHOLE_INDEX) ||
3536
found_part == PREV_BITS(uint, keyinfo->key_parts)))
3538
max_key_part= max_part_bit(found_part);
3540
ReuseRangeEstimateForRef-3:
3541
We're now considering a ref[or_null] access via
3542
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
3543
(same-as-above but with one cond replaced
3544
with "t.keypart_i IS NULL")] (**)
3546
Try re-using E(#rows) from "range" optimizer:
3547
We can do so if "range" optimizer used the same intervals as
3548
in (**). The intervals used by range optimizer may be not
3549
available at this point (as "range" access might have choosen to
3550
create quick select over another index), so we can't compare
3551
them to (**). We'll make indirect judgements instead.
3552
The sufficient conditions for re-use are:
3553
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
3554
this is not satisfied we have no way to know which ranges
3555
will be actually scanned by 'ref' until we execute the
3557
(C2) max #key parts in 'range' access == K == max_key_part (this
3558
is apparently a necessary requirement)
3560
We also have a property that "range optimizer produces equal or
3561
tighter set of scan intervals than ref(const) optimizer". Each
3562
of the intervals in (**) are "tightest possible" intervals when
3563
one limits itself to using keyparts 1..K (which we do in #2).
3564
From here it follows that range access used either one, or
3565
both of the (I1) and (I2) intervals:
3567
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
3568
(same-as-above but with one cond replaced
3569
with "t.keypart_i IS NULL") (I2)
3571
The remaining part is to exclude the situation where range
3572
optimizer used one interval while we're considering
3573
ref-or-null and looking for estimate for two intervals. This
3574
is done by last limitation:
3576
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
3578
if (table->quick_keys.test(key) && !found_ref && //(C1)
3579
table->quick_key_parts[key] == max_key_part && //(C2)
3580
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
3582
tmp= records= (double) table->quick_rows[key];
3586
/* Check if we have statistic about the distribution */
3587
if ((records= keyinfo->rec_per_key[max_key_part-1]))
3590
Fix for the case where the index statistics is too
3592
(1) We're considering ref(const) and there is quick select
3594
(2) and that quick select uses more keyparts (i.e. it will
3595
scan equal/smaller interval then this ref(const))
3596
(3) and E(#rows) for quick select is higher then our
3599
We'll use E(#rows) from quick select.
3601
Q: Why do we choose to use 'ref'? Won't quick select be
3602
cheaper in some cases ?
3603
TODO: figure this out and adjust the plan choice if needed.
3605
if (!found_ref && table->quick_keys.test(key) && // (1)
3606
table->quick_key_parts[key] > max_key_part && // (2)
3607
records < (double)table->quick_rows[key]) // (3)
3608
records= (double)table->quick_rows[key];
3615
Assume that the first key part matches 1% of the cursor
3616
and that the whole key matches 10 (duplicates) or 1
3618
Assume also that more key matches proportionally more
3620
This gives the formula:
3621
records = (x * (b-a) + a*c-b)/(c-1)
3623
b = records matched by whole key
3624
a = records matched by first key part (1% of all records?)
3625
c = number of key parts in key
3626
x = used key parts (1 <= x <= c)
3629
if (!(rec_per_key=(double)
3630
keyinfo->rec_per_key[keyinfo->key_parts-1]))
3631
rec_per_key=(double) s->records/rec+1;
3635
else if (rec_per_key/(double) s->records >= 0.01)
3639
double a=s->records*0.01;
3640
if (keyinfo->key_parts > 1)
3641
tmp= (max_key_part * (rec_per_key - a) +
3642
a*keyinfo->key_parts - rec_per_key)/
3643
(keyinfo->key_parts-1);
3646
set_if_bigger(tmp,1.0);
3648
records = (uint32_t) tmp;
3651
if (ref_or_null_part)
3653
/* We need to do two key searches to find key */
3659
ReuseRangeEstimateForRef-4: We get here if we could not reuse
3660
E(#rows) from range optimizer. Make another try:
3662
If range optimizer produced E(#rows) for a prefix of the ref
3663
access we're considering, and that E(#rows) is lower then our
3664
current estimate, make the adjustment.
3666
The decision whether we can re-use the estimate from the range
3667
optimizer is the same as in ReuseRangeEstimateForRef-3,
3668
applied to first table->quick_key_parts[key] key parts.
3670
if (table->quick_keys.test(key) &&
3671
table->quick_key_parts[key] <= max_key_part &&
3672
const_part & (1 << table->quick_key_parts[key]) &&
3673
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
3674
const_part) ? 1 : 0) &&
3675
records > (double) table->quick_rows[key])
3677
tmp= records= (double) table->quick_rows[key];
3681
/* Limit the number of matched rows */
3682
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3683
if (table->covering_keys.test(key))
3685
/* we can use only index tree */
3686
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3689
tmp= record_count * min(tmp,s->worst_seeks);
3692
tmp= best_time; // Do nothing
3696
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
3698
best_time= tmp + records/(double) TIME_FOR_COMPARE;
3700
best_records= records;
3701
best_key= start_key;
3702
best_max_key_part= max_key_part;
3703
best_ref_depends_map= found_ref;
3706
records= best_records;
3710
Don't test table scan if it can't be better.
3711
Prefer key lookup if we would use the same key for scanning.
3713
Don't do a table scan on InnoDB tables, if we can read the used
3714
parts of the row from any of the used index.
3715
This is because table scans uses index and we would not win
3716
anything by using a table scan.
3718
A word for word translation of the below if-statement in sergefp's
3719
understanding: we check if we should use table scan if:
3720
(1) The found 'ref' access produces more records than a table scan
3721
(or index scan, or quick select), or 'ref' is more expensive than
3723
(2) This doesn't hold: the best way to perform table scan is to to perform
3724
'range' access using index IDX, and the best way to perform 'ref'
3725
access is to use the same index IDX, with the same or more key parts.
3726
(note: it is not clear how this rule is/should be extended to
3727
index_merge quick selects)
3728
(3) See above note about InnoDB.
3729
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
3730
path, but there is no quick select)
3731
If the condition in the above brackets holds, then the only possible
3732
"table scan" access method is ALL/index (there is no quick select).
3733
Since we have a 'ref' access path, and FORCE INDEX instructs us to
3734
choose it over ALL/index, there is no need to consider a full table
3737
if ((records >= s->found_records || best > s->read_time) && // (1)
3738
! (s->quick && best_key && s->quick->index == best_key->getKey() && // (2)
3739
best_max_key_part >= s->table->quick_key_parts[best_key->getKey()]) &&// (2)
3740
! ((s->table->cursor->getEngine()->check_flag(HTON_BIT_TABLE_SCAN_ON_INDEX)) && // (3)
3741
! s->table->covering_keys.none() && best_key && !s->quick) && // (3)
3742
! (s->table->force_index && best_key && !s->quick)) // (4)
3743
{ // Check full join
3744
ha_rows rnd_records= s->found_records;
3746
If there is a filtering condition on the table (i.e. ref analyzer found
3747
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
3748
preceding this table in the join order we're now considering), then
3749
assume that 25% of the rows will be filtered out by this condition.
3751
This heuristic is supposed to force tables used in exprZ to be before
3752
this table in join order.
3754
if (found_constraint)
3755
rnd_records-= rnd_records/4;
3758
If applicable, get a more accurate estimate. Don't use the two
3761
if (s->table->quick_condition_rows != s->found_records)
3762
rnd_records= s->table->quick_condition_rows;
3765
Range optimizer never proposes a RANGE if it isn't better
3766
than FULL: so if RANGE is present, it's always preferred to FULL.
3767
Here we estimate its cost.
3773
- read record range through 'quick'
3774
- skip rows which does not satisfy WHERE constraints
3776
We take into account possible use of join cache for ALL/index
3777
access (see first else-branch below), but we don't take it into
3778
account here for range/index_merge access. Find out why this is so.
3781
(s->quick->read_time +
3782
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
3786
/* Estimate cost of reading table. */
3787
tmp= s->table->cursor->scan_time();
3788
if (s->table->map & join->outer_join) // Can't use join cache
3791
For each record we have to:
3792
- read the whole table record
3793
- skip rows which does not satisfy join condition
3797
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
3801
/* We read the table as many times as join buffer becomes full. */
3802
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
3804
(double) session->variables.join_buff_size));
3806
We don't make full cartesian product between rows in the scanned
3807
table and existing records because we skip all rows from the
3808
scanned table, which does not satisfy join condition when
3809
we read the table (see flush_cached_records for details). Here we
3810
take into account cost to read and skip these records.
3812
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
3817
We estimate the cost of evaluating WHERE clause for found records
3818
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
3819
tmp give us total cost of using Table SCAN
3821
if (best == DBL_MAX ||
3822
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
3823
best + record_count/(double) TIME_FOR_COMPARE*records))
3826
If the table has a range (s->quick is set) make_join_select()
3827
will ensure that this will be used
3830
records= rows2double(rnd_records);
3832
/* range/index_merge/ALL/index access method are "independent", so: */
3833
best_ref_depends_map= 0;
3837
/* Update the cost information for the current partial plan */
3838
optimizer::Position tmp_pos(records,
3842
best_ref_depends_map);
3843
join->setPosInPartialPlan(idx, tmp_pos);
3846
idx == join->const_tables &&
3847
s->table == join->sort_by_table &&
3848
join->unit->select_limit_cnt >= records)
3849
join->sort_by_table= (Table*) 1; // Must use temporary table
3855
Select the best ways to access the tables in a query without reordering them.
3857
Find the best access paths for each query table and compute their costs
3858
according to their order in the array 'join->best_ref' (thus without
3859
reordering the join tables). The function calls sequentially
3860
'best_access_path' for each table in the query to select the best table
3861
access method. The final optimal plan is stored in the array
3862
'join->best_positions', and the corresponding cost in 'join->best_read'.
3864
@param join pointer to the structure providing all context info for
3866
@param join_tables set of the tables in the query
3869
This function can be applied to:
3870
- queries with STRAIGHT_JOIN
3871
- internally to compute the cost of an arbitrary QEP
3873
Thus 'optimize_straight_join' can be used at any stage of the query
3874
optimization process to finalize a QEP as it is.
3876
static void optimize_straight_join(JOIN *join, table_map join_tables)
3879
optimizer::Position partial_pos;
3880
uint32_t idx= join->const_tables;
3881
double record_count= 1.0;
3882
double read_time= 0.0;
3884
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
3886
/* Find the best access method from 's' to the current partial plan */
3887
best_access_path(join, s, join->session, join_tables, idx,
3888
record_count, read_time);
3889
/* compute the cost of the new plan extended with 's' */
3890
partial_pos= join->getPosFromPartialPlan(idx);
3891
record_count*= partial_pos.getFanout();
3892
read_time+= partial_pos.getCost();
3893
join_tables&= ~(s->table->map);
3897
read_time+= record_count / (double) TIME_FOR_COMPARE;
3898
partial_pos= join->getPosFromPartialPlan(join->const_tables);
3899
if (join->sort_by_table &&
3900
partial_pos.hasTableForSorting(join->sort_by_table))
3901
read_time+= record_count; // We have to make a temp table
3902
join->copyPartialPlanIntoOptimalPlan(idx);
3903
join->best_read= read_time;
3907
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
3909
The search procedure uses a hybrid greedy/exhaustive search with controlled
3910
exhaustiveness. The search is performed in N = card(remaining_tables)
3911
steps. Each step evaluates how promising is each of the unoptimized tables,
3912
selects the most promising table, and extends the current partial QEP with
3913
that table. Currenly the most 'promising' table is the one with least
3914
expensive extension.\
3916
There are two extreme cases:
3917
-# When (card(remaining_tables) < search_depth), the estimate finds the
3918
best complete continuation of the partial QEP. This continuation can be
3919
used directly as a result of the search.
3920
-# When (search_depth == 1) the 'best_extension_by_limited_search'
3921
consideres the extension of the current QEP with each of the remaining
3924
All other cases are in-between these two extremes. Thus the parameter
3925
'search_depth' controlls the exhaustiveness of the search. The higher the
3926
value, the longer the optimizaton time and possibly the better the
3927
resulting plan. The lower the value, the fewer alternative plans are
3928
estimated, but the more likely to get a bad QEP.
3930
All intermediate and final results of the procedure are stored in 'join':
3931
- join->positions : modified for every partial QEP that is explored
3932
- join->best_positions: modified for the current best complete QEP
3933
- join->best_read : modified for the current best complete QEP
3934
- join->best_ref : might be partially reordered
3936
The final optimal plan is stored in 'join->best_positions', and its
3937
corresponding cost in 'join->best_read'.
3940
The following pseudocode describes the algorithm of 'greedy_search':
3943
procedure greedy_search
3944
input: remaining_tables
3949
(t, a) = best_extension(pplan, remaining_tables);
3950
pplan = concat(pplan, (t, a));
3951
remaining_tables = remaining_tables - t;
3952
} while (remaining_tables != {})
3957
where 'best_extension' is a placeholder for a procedure that selects the
3958
most "promising" of all tables in 'remaining_tables'.
3959
Currently this estimate is performed by calling
3960
'best_extension_by_limited_search' to evaluate all extensions of the
3961
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
3962
mainly depends on that of 'best_extension_by_limited_search'.
3965
If 'best_extension()' == 'best_extension_by_limited_search()', then the
3966
worst-case complexity of this algorithm is <=
3967
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
3968
complexity of greedy_search is O(N!).
3971
In the future, 'greedy_search' might be extended to support other
3972
implementations of 'best_extension', e.g. some simpler quadratic procedure.
3974
@param join pointer to the structure providing all context info
3976
@param remaining_tables set of tables not included into the partial plan yet
3977
@param search_depth controlls the exhaustiveness of the search
3978
@param prune_level the pruning heuristics that should be applied during
3986
static bool greedy_search(JOIN *join,
3987
table_map remaining_tables,
3988
uint32_t search_depth,
3989
uint32_t prune_level)
3991
double record_count= 1.0;
3992
double read_time= 0.0;
3993
uint32_t idx= join->const_tables; // index into 'join->best_ref'
3995
uint32_t size_remain; // cardinality of remaining_tables
3996
optimizer::Position best_pos;
3997
JoinTable *best_table; // the next plan node to be added to the curr QEP
3999
/* number of tables that remain to be optimized */
4000
size_remain= my_count_bits(remaining_tables);
4003
/* Find the extension of the current QEP with the lowest cost */
4004
join->best_read= DBL_MAX;
4005
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
4006
read_time, search_depth, prune_level))
4009
if (size_remain <= search_depth)
4012
'join->best_positions' contains a complete optimal extension of the
4013
current partial QEP.
4018
/* select the first table in the optimal extension as most promising */
4019
best_pos= join->getPosFromOptimalPlan(idx);
4020
best_table= best_pos.getJoinTable();
4022
Each subsequent loop of 'best_extension_by_limited_search' uses
4023
'join->positions' for cost estimates, therefore we have to update its
4026
join->setPosInPartialPlan(idx, best_pos);
4028
/* find the position of 'best_table' in 'join->best_ref' */
4030
JoinTable *pos= join->best_ref[best_idx];
4031
while (pos && best_table != pos)
4032
pos= join->best_ref[++best_idx];
4033
assert((pos != NULL)); // should always find 'best_table'
4034
/* move 'best_table' at the first free position in the array of joins */
4035
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
4037
/* compute the cost of the new plan extended with 'best_table' */
4038
optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
4039
record_count*= partial_pos.getFanout();
4040
read_time+= partial_pos.getCost();
4042
remaining_tables&= ~(best_table->table->map);
4050
Find a good, possibly optimal, query execution plan (QEP) by a possibly
4053
The procedure searches for the optimal ordering of the query tables in set
4054
'remaining_tables' of size N, and the corresponding optimal access paths to
4055
each table. The choice of a table order and an access path for each table
4056
constitutes a query execution plan (QEP) that fully specifies how to
4059
The maximal size of the found plan is controlled by the parameter
4060
'search_depth'. When search_depth == N, the resulting plan is complete and
4061
can be used directly as a QEP. If search_depth < N, the found plan consists
4062
of only some of the query tables. Such "partial" optimal plans are useful
4063
only as input to query optimization procedures, and cannot be used directly
4066
The algorithm begins with an empty partial plan stored in 'join->positions'
4067
and a set of N tables - 'remaining_tables'. Each step of the algorithm
4068
evaluates the cost of the partial plan extended by all access plans for
4069
each of the relations in 'remaining_tables', expands the current partial
4070
plan with the access plan that results in lowest cost of the expanded
4071
partial plan, and removes the corresponding relation from
4072
'remaining_tables'. The algorithm continues until it either constructs a
4073
complete optimal plan, or constructs an optimal plartial plan with size =
4076
The final optimal plan is stored in 'join->best_positions'. The
4077
corresponding cost of the optimal plan is in 'join->best_read'.
4080
The procedure uses a recursive depth-first search where the depth of the
4081
recursion (and thus the exhaustiveness of the search) is controlled by the
4082
parameter 'search_depth'.
4085
The pseudocode below describes the algorithm of
4086
'best_extension_by_limited_search'. The worst-case complexity of this
4087
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
4088
the complexity of greedy_search is O(N!).
4091
procedure best_extension_by_limited_search(
4092
pplan in, // in, partial plan of tables-joined-so-far
4093
pplan_cost, // in, cost of pplan
4094
remaining_tables, // in, set of tables not referenced in pplan
4095
best_plan_so_far, // in/out, best plan found so far
4096
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
4097
search_depth) // in, maximum size of the plans being considered
4099
for each table T from remaining_tables
4101
// Calculate the cost of using table T as above
4102
cost = complex-series-of-calculations;
4104
// Add the cost to the cost so far.
4107
if (pplan_cost >= best_plan_so_far_cost)
4108
// pplan_cost already too great, stop search
4111
pplan= expand pplan by best_access_method;
4112
remaining_tables= remaining_tables - table T;
4113
if (remaining_tables is not an empty set
4117
best_extension_by_limited_search(pplan, pplan_cost,
4120
best_plan_so_far_cost,
4125
best_plan_so_far_cost= pplan_cost;
4126
best_plan_so_far= pplan;
4133
When 'best_extension_by_limited_search' is called for the first time,
4134
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
4135
The actual implementation provides a way to optionally use pruning
4136
heuristic (controlled by the parameter 'prune_level') to reduce the search
4137
space by skipping some partial plans.
4140
The parameter 'search_depth' provides control over the recursion
4141
depth, and thus the size of the resulting optimal plan.
4143
@param join pointer to the structure providing all context info
4145
@param remaining_tables set of tables not included into the partial plan yet
4146
@param idx length of the partial QEP in 'join->positions';
4147
since a depth-first search is used, also corresponds
4148
to the current depth of the search tree;
4149
also an index in the array 'join->best_ref';
4150
@param record_count estimate for the number of records returned by the
4152
@param read_time the cost of the best partial plan
4153
@param search_depth maximum depth of the recursion and thus size of the
4155
(0 < search_depth <= join->tables+1).
4156
@param prune_level pruning heuristics that should be applied during
4158
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
4165
static bool best_extension_by_limited_search(JOIN *join,
4166
table_map remaining_tables,
4168
double record_count,
4170
uint32_t search_depth,
4171
uint32_t prune_level)
4173
Session *session= join->session;
4174
if (session->killed) // Abort
4178
'join' is a partial plan with lower cost than the best plan so far,
4179
so continue expanding it further with the tables in 'remaining_tables'.
4182
double best_record_count= DBL_MAX;
4183
double best_read_time= DBL_MAX;
4184
optimizer::Position partial_pos;
4186
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4188
table_map real_table_bit= s->table->map;
4191
partial_pos= join->getPosFromPartialPlan(idx - 1);
4193
if ((remaining_tables & real_table_bit) &&
4194
! (remaining_tables & s->dependent) &&
4195
(! idx || ! check_interleaving_with_nj(partial_pos.getJoinTable(), s)))
4197
double current_record_count, current_read_time;
4200
psergey-insideout-todo:
4201
when best_access_path() detects it could do an InsideOut scan or
4202
some other scan, have it return an insideout scan and a flag that
4203
requests to "fork" this loop iteration. (Q: how does that behave
4204
when the depth is insufficient??)
4206
/* Find the best access method from 's' to the current partial plan */
4207
best_access_path(join, s, session, remaining_tables, idx,
4208
record_count, read_time);
4209
/* Compute the cost of extending the plan with 's' */
4210
partial_pos= join->getPosFromPartialPlan(idx);
4211
current_record_count= record_count * partial_pos.getFanout();
4212
current_read_time= read_time + partial_pos.getCost();
4214
/* Expand only partial plans with lower cost than the best QEP so far */
4215
if ((current_read_time +
4216
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
4218
restore_prev_nj_state(s);
4223
Prune some less promising partial plans. This heuristic may miss
4224
the optimal QEPs, thus it results in a non-exhaustive search.
4226
if (prune_level == 1)
4228
if (best_record_count > current_record_count ||
4229
best_read_time > current_read_time ||
4230
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
4232
if (best_record_count >= current_record_count &&
4233
best_read_time >= current_read_time &&
4234
/* TODO: What is the reasoning behind this condition? */
4235
(! (s->key_dependent & remaining_tables) ||
4236
partial_pos.isConstTable()))
4238
best_record_count= current_record_count;
4239
best_read_time= current_read_time;
4244
restore_prev_nj_state(s);
4249
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
4250
{ /* Recursively expand the current partial plan */
4251
std::swap(join->best_ref[idx], *pos);
4252
if (best_extension_by_limited_search(join,
4253
remaining_tables & ~real_table_bit,
4255
current_record_count,
4260
std::swap(join->best_ref[idx], *pos);
4264
'join' is either the best partial QEP with 'search_depth' relations,
4265
or the best complete QEP so far, whichever is smaller.
4267
partial_pos= join->getPosFromPartialPlan(join->const_tables);
4268
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4269
if (join->sort_by_table &&
4270
partial_pos.hasTableForSorting(join->sort_by_table))
4271
/* We have to make a temp table */
4272
current_read_time+= current_record_count;
4273
if ((search_depth == 1) || (current_read_time < join->best_read))
4275
join->copyPartialPlanIntoOptimalPlan(idx + 1);
4276
join->best_read= current_read_time - 0.001;
4279
restore_prev_nj_state(s);
4286
Heuristic procedure to automatically guess a reasonable degree of
4287
exhaustiveness for the greedy search procedure.
4289
The procedure estimates the optimization time and selects a search depth
4290
big enough to result in a near-optimal QEP, that doesn't take too long to
4291
find. If the number of tables in the query exceeds some constant, then
4292
search_depth is set to this constant.
4294
@param join pointer to the structure providing all context info for
4298
This is an extremely simplistic implementation that serves as a stub for a
4299
more advanced analysis of the join. Ideally the search depth should be
4300
determined by learning from previous query optimizations, because it will
4301
depend on the CPU power (and other factors).
4304
this value should be determined dynamically, based on statistics:
4305
uint32_t max_tables_for_exhaustive_opt= 7;
4308
this value could be determined by some mapping of the form:
4309
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4312
A positive integer that specifies the search depth (and thus the
4313
exhaustiveness) of the depth-first search algorithm used by
4316
static uint32_t determine_search_depth(JOIN *join)
4318
uint32_t table_count= join->tables - join->const_tables;
4319
uint32_t search_depth;
4320
/* TODO: this value should be determined dynamically, based on statistics: */
4321
uint32_t max_tables_for_exhaustive_opt= 7;
4323
if (table_count <= max_tables_for_exhaustive_opt)
4324
search_depth= table_count+1; // use exhaustive for small number of tables
4327
TODO: this value could be determined by some mapping of the form:
4328
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4330
search_depth= max_tables_for_exhaustive_opt; // use greedy search
4332
return search_depth;
4335
static bool make_simple_join(JOIN *join,Table *tmp_table)
4338
JoinTable *join_tab;
4341
Reuse Table * and JoinTable if already allocated by a previous call
4342
to this function through JOIN::exec (may happen for sub-queries).
4344
if (!join->table_reexec)
4346
if (!(join->table_reexec= (Table**) join->session->alloc(sizeof(Table*))))
4349
join->tmp_join->table_reexec= join->table_reexec;
4351
if (!join->join_tab_reexec)
4353
if (!(join->join_tab_reexec=
4354
(JoinTable*) join->session->alloc(sizeof(JoinTable))))
4357
join->tmp_join->join_tab_reexec= join->join_tab_reexec;
4359
tableptr= join->table_reexec;
4360
join_tab= join->join_tab_reexec;
4362
join->join_tab=join_tab;
4363
join->table=tableptr; tableptr[0]=tmp_table;
4365
join->const_tables=0;
4366
join->const_table_map=0;
4367
join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=
4368
join->tmp_table_param.func_count=0;
4369
join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;
4370
join->first_record=join->sort_and_group=0;
4371
join->send_records=(ha_rows) 0;
4373
join->row_limit=join->unit->select_limit_cnt;
4374
join->do_send_rows = (join->row_limit) ? 1 : 0;
4376
join_tab->cache.buff=0; /* No caching */
4377
join_tab->table=tmp_table;
4379
join_tab->select_cond=0;
4381
join_tab->type= AM_ALL; /* Map through all records */
4382
join_tab->keys.set(); /* test everything in quick */
4384
join_tab->on_expr_ref=0;
4385
join_tab->last_inner= 0;
4386
join_tab->first_unmatched= 0;
4387
join_tab->ref.key = -1;
4388
join_tab->not_used_in_distinct=0;
4389
join_tab->read_first_record= join_init_read_record;
4390
join_tab->join=join;
4391
join_tab->ref.key_parts= 0;
4392
memset(&join_tab->read_record, 0, sizeof(join_tab->read_record));
4393
tmp_table->status=0;
4394
tmp_table->null_row=0;
4399
Fill in outer join related info for the execution plan structure.
4401
For each outer join operation left after simplification of the
4402
original query the function set up the following pointers in the linear
4403
structure join->join_tab representing the selected execution plan.
4404
The first inner table t0 for the operation is set to refer to the last
4405
inner table tk through the field t0->last_inner.
4406
Any inner table ti for the operation are set to refer to the first
4407
inner table ti->first_inner.
4408
The first inner table t0 for the operation is set to refer to the
4409
first inner table of the embedding outer join operation, if there is any,
4410
through the field t0->first_upper.
4411
The on expression for the outer join operation is attached to the
4412
corresponding first inner table through the field t0->on_expr_ref.
4413
Here ti are structures of the JoinTable type.
4415
EXAMPLE. For the query:
4419
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
4420
ON (t1.a=t2.a AND t1.b=t3.b)
4424
given the execution plan with the table order t1,t2,t3,t4
4425
is selected, the following references will be set;
4426
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
4427
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
4428
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
4429
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
4431
@param join reference to the info fully describing the query
4434
The function assumes that the simplification procedure has been
4435
already applied to the join query (see simplify_joins).
4436
This function can be called only after the execution plan
4439
static void make_outerjoin_info(JOIN *join)
4441
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4443
JoinTable *tab=join->join_tab+i;
4444
Table *table=tab->table;
4445
TableList *tbl= table->pos_in_table_list;
4446
TableList *embedding= tbl->embedding;
4448
if (tbl->outer_join)
4451
Table tab is the only one inner table for outer join.
4452
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
4453
is in the query above.)
4455
tab->last_inner= tab->first_inner= tab;
4456
tab->on_expr_ref= &tbl->on_expr;
4457
tab->cond_equal= tbl->cond_equal;
4459
tab->first_upper= embedding->nested_join->first_nested;
4461
for ( ; embedding ; embedding= embedding->embedding)
4463
/* Ignore sj-nests: */
4464
if (!embedding->on_expr)
4466
nested_join_st *nested_join= embedding->nested_join;
4467
if (!nested_join->counter_)
4470
Table tab is the first inner table for nested_join.
4471
Save reference to it in the nested join structure.
4473
nested_join->first_nested= tab;
4474
tab->on_expr_ref= &embedding->on_expr;
4475
tab->cond_equal= tbl->cond_equal;
4476
if (embedding->embedding)
4477
tab->first_upper= embedding->embedding->nested_join->first_nested;
4479
if (!tab->first_inner)
4480
tab->first_inner= nested_join->first_nested;
4481
if (++nested_join->counter_ < nested_join->join_list.elements)
4483
/* Table tab is the last inner table for nested join. */
4484
nested_join->first_nested->last_inner= tab;
4490
static bool make_join_select(JOIN *join,
4491
optimizer::SqlSelect *select,
4494
Session *session= join->session;
4495
optimizer::Position cur_pos;
4498
add_not_null_conds(join);
4499
table_map used_tables;
4500
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
4501
{ /* there may be a select without a cond. */
4502
if (join->tables > 1)
4503
cond->update_used_tables(); // Tablenr may have changed
4504
if (join->const_tables == join->tables &&
4505
session->lex->current_select->master_unit() ==
4506
&session->lex->unit) // not upper level SELECT
4507
join->const_table_map|=RAND_TABLE_BIT;
4508
{ // Check const tables
4510
make_cond_for_table(cond,
4511
join->const_table_map,
4513
for (JoinTable *tab= join->join_tab+join->const_tables;
4514
tab < join->join_tab+join->tables ; tab++)
4516
if (*tab->on_expr_ref)
4518
JoinTable *cond_tab= tab->first_inner;
4519
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
4520
join->const_table_map,
4524
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4527
tmp->quick_fix_field();
4528
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4529
new Item_cond_and(cond_tab->select_cond,
4531
if (! cond_tab->select_cond)
4533
cond_tab->select_cond->quick_fix_field();
4536
if (const_cond && ! const_cond->val_int())
4538
return 1; // Impossible const condition
4542
used_tables=((select->const_tables=join->const_table_map) |
4543
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4544
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4546
JoinTable *tab=join->join_tab+i;
4548
first_inner is the X in queries like:
4549
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
4551
JoinTable *first_inner_tab= tab->first_inner;
4552
table_map current_map= tab->table->map;
4553
bool use_quick_range=0;
4557
Following force including random expression in last table condition.
4558
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
4560
if (i == join->tables-1)
4561
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
4562
used_tables|=current_map;
4564
if (tab->type == AM_REF && tab->quick &&
4565
(uint32_t) tab->ref.key == tab->quick->index &&
4566
tab->ref.key_length < tab->quick->max_used_key_length)
4568
/* Range uses longer key; Use this instead of ref on key */
4573
tab->ref.key_parts= 0; // Don't use ref key.
4574
cur_pos= join->getPosFromOptimalPlan(i);
4575
cur_pos.setFanout(rows2double(tab->quick->records));
4577
We will use join cache here : prevent sorting of the first
4578
table only and sort at the end.
4580
if (i != join->const_tables && join->tables > join->const_tables + 1)
4586
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
4587
if (cond && !tmp && tab->quick)
4589
if (tab->type != AM_ALL)
4592
Don't use the quick method
4593
We come here in the case where we have 'key=constant' and
4594
the test is removed by make_cond_for_table()
4602
Hack to handle the case where we only refer to a table
4603
in the ON part of an OUTER JOIN. In this case we want the code
4604
below to check if we should use 'quick' instead.
4606
tmp= new Item_int((int64_t) 1,1); // Always true
4610
if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||
4611
tab->type == AM_EQ_REF)
4613
optimizer::SqlSelect *sel= tab->select= ((optimizer::SqlSelect*)
4614
session->memdup((unsigned char*) select,
4617
return 1; // End of memory
4619
If tab is an inner table of an outer join operation,
4620
add a match guard to the pushed down predicate.
4621
The guard will turn the predicate on only after
4622
the first match for outer tables is encountered.
4627
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
4628
a cond, so neutralize the hack above.
4630
if (! (tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
4632
tab->select_cond=sel->cond=tmp;
4635
tab->select_cond= sel->cond= NULL;
4637
sel->head=tab->table;
4640
/* Use quick key read if it's a constant and it's not used
4642
if (tab->needed_reg.none() && tab->type != AM_EQ_REF
4643
&& (tab->type != AM_REF || (uint32_t) tab->ref.key == tab->quick->index))
4645
sel->quick=tab->quick; // Use value from get_quick_...
4646
sel->quick_keys.reset();
4647
sel->needed_reg.reset();
4655
uint32_t ref_key= static_cast<uint32_t>(sel->head->reginfo.join_tab->ref.key + 1);
4656
if (i == join->const_tables && ref_key)
4658
if (tab->const_keys.any() &&
4659
tab->table->reginfo.impossible_range)
4662
else if (tab->type == AM_ALL && ! use_quick_range)
4664
if (tab->const_keys.any() &&
4665
tab->table->reginfo.impossible_range)
4666
return 1; // Impossible range
4668
We plan to scan all rows.
4669
Check again if we should use an index.
4670
We could have used an column from a previous table in
4671
the index if we are using limit and this is the first table
4674
cur_pos= join->getPosFromOptimalPlan(i);
4675
if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
4676
(! tab->const_keys.none() && (i == join->const_tables) &&
4677
(join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4679
/* Join with outer join condition */
4680
COND *orig_cond= sel->cond;
4681
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
4684
We can't call sel->cond->fix_fields,
4685
as it will break tab->on_expr if it's AND condition
4686
(fix_fields currently removes extra AND/OR levels).
4687
Yet attributes of the just built condition are not needed.
4688
Thus we call sel->cond->quick_fix_field for safety.
4690
if (sel->cond && ! sel->cond->fixed)
4691
sel->cond->quick_fix_field();
4693
if (sel->test_quick_select(session, tab->keys,
4694
used_tables & ~ current_map,
4695
(join->select_options &
4698
join->unit->select_limit_cnt), 0,
4702
Before reporting "Impossible WHERE" for the whole query
4703
we have to check isn't it only "impossible ON" instead
4705
sel->cond=orig_cond;
4706
if (! *tab->on_expr_ref ||
4707
sel->test_quick_select(session, tab->keys,
4708
used_tables & ~ current_map,
4709
(join->select_options &
4712
join->unit->select_limit_cnt),0,
4714
return 1; // Impossible WHERE
4717
sel->cond=orig_cond;
4719
/* Fix for EXPLAIN */
4722
cur_pos= join->getPosFromOptimalPlan(i);
4723
cur_pos.setFanout(static_cast<double>(sel->quick->records));
4728
sel->needed_reg= tab->needed_reg;
4729
sel->quick_keys.reset();
4731
if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
4732
!((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
4734
tab->keys= sel->quick_keys;
4735
tab->keys|= sel->needed_reg;
4736
tab->use_quick= (!sel->needed_reg.none() &&
4737
(select->quick_keys.none() ||
4739
(select->quick->records >= 100L)))) ?
4741
sel->read_tables= used_tables & ~current_map;
4743
if (i != join->const_tables && tab->use_quick != 2)
4744
{ /* Read with cache */
4746
(tmp=make_cond_for_table(cond,
4747
join->const_table_map |
4751
tab->cache.select= (optimizer::SqlSelect*)
4752
session->memdup((unsigned char*) sel, sizeof(optimizer::SqlSelect));
4753
tab->cache.select->cond= tmp;
4754
tab->cache.select->read_tables= join->const_table_map;
4761
Push down conditions from all on expressions.
4762
Each of these conditions are guarded by a variable
4763
that turns if off just before null complemented row for
4764
outer joins is formed. Thus, the condition from an
4765
'on expression' are guaranteed not to be checked for
4766
the null complemented row.
4769
/* First push down constant conditions from on expressions */
4770
for (JoinTable *join_tab= join->join_tab+join->const_tables;
4771
join_tab < join->join_tab+join->tables ; join_tab++)
4773
if (*join_tab->on_expr_ref)
4775
JoinTable *cond_tab= join_tab->first_inner;
4776
tmp= make_cond_for_table(*join_tab->on_expr_ref,
4777
join->const_table_map,
4781
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4784
tmp->quick_fix_field();
4785
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4786
new Item_cond_and(cond_tab->select_cond,tmp);
4787
if (! cond_tab->select_cond)
4789
cond_tab->select_cond->quick_fix_field();
4793
/* Push down non-constant conditions from on expressions */
4794
JoinTable *last_tab= tab;
4795
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
4798
Table tab is the last inner table of an outer join.
4799
An on expression is always attached to it.
4801
COND *on_expr= *first_inner_tab->on_expr_ref;
4803
table_map used_tables2= (join->const_table_map |
4804
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4805
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
4807
current_map= tab->table->map;
4808
used_tables2|= current_map;
4809
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
4813
JoinTable *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
4815
First add the guards for match variables of
4816
all embedding outer join operations.
4818
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
4823
Now add the guard turning the predicate off for
4824
the null complemented row.
4826
tmp_cond= new Item_func_trig_cond(tmp_cond,
4830
tmp_cond->quick_fix_field();
4831
/* Add the predicate to other pushed down predicates */
4832
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
4833
new Item_cond_and(cond_tab->select_cond,
4835
if (! cond_tab->select_cond)
4837
cond_tab->select_cond->quick_fix_field();
4840
first_inner_tab= first_inner_tab->first_upper;
4848
Plan refinement stage: do various set ups for the executioner
4851
make_join_readinfo()
4852
join Join being processed
4853
options Join's options (checking for SELECT_DESCRIBE,
4854
SELECT_NO_JOIN_CACHE)
4855
no_jbuf_after Don't use join buffering after table with this number.
4858
Plan refinement stage: do various set ups for the executioner
4859
- set up use of join buffering
4860
- push index conditions
4861
- increment counters
4866
true - Out of memory
4868
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
4871
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
4874
for (i=join->const_tables ; i < join->tables ; i++)
4876
JoinTable *tab=join->join_tab+i;
4877
Table *table=tab->table;
4878
bool using_join_cache;
4879
tab->read_record.table= table;
4880
tab->read_record.cursor= table->cursor;
4881
tab->next_select=sub_select; /* normal select */
4883
TODO: don't always instruct first table's ref/range access method to
4884
produce sorted output.
4886
tab->sorted= sorted;
4887
sorted= 0; // only first must be sorted
4888
if (tab->insideout_match_tab)
4890
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
4895
switch (tab->type) {
4896
case AM_SYSTEM: // Only happens with left join
4897
table->status=STATUS_NO_RECORD;
4898
tab->read_first_record= join_read_system;
4899
tab->read_record.read_record= join_no_more_records;
4901
case AM_CONST: // Only happens with left join
4902
table->status=STATUS_NO_RECORD;
4903
tab->read_first_record= join_read_const;
4904
tab->read_record.read_record= join_no_more_records;
4905
if (table->covering_keys.test(tab->ref.key) &&
4909
table->cursor->extra(HA_EXTRA_KEYREAD);
4913
table->status=STATUS_NO_RECORD;
4916
delete tab->select->quick;
4917
tab->select->quick=0;
4921
tab->read_first_record= join_read_key;
4922
tab->read_record.read_record= join_no_more_records;
4923
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4926
table->cursor->extra(HA_EXTRA_KEYREAD);
4929
case AM_REF_OR_NULL:
4931
table->status=STATUS_NO_RECORD;
4934
delete tab->select->quick;
4935
tab->select->quick=0;
4939
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4942
table->cursor->extra(HA_EXTRA_KEYREAD);
4944
if (tab->type == AM_REF)
4946
tab->read_first_record= join_read_always_key;
4947
tab->read_record.read_record= tab->insideout_match_tab?
4948
join_read_next_same_diff : join_read_next_same;
4952
tab->read_first_record= join_read_always_key_or_null;
4953
tab->read_record.read_record= join_read_next_same_or_null;
4958
If previous table use cache
4959
If the incoming data set is already sorted don't use cache.
4961
table->status=STATUS_NO_RECORD;
4962
using_join_cache= false;
4963
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
4964
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
4965
!tab->insideout_match_tab)
4967
if ((options & SELECT_DESCRIBE) ||
4968
!join_init_cache(join->session,join->join_tab+join->const_tables,
4969
i-join->const_tables))
4971
using_join_cache= true;
4972
tab[-1].next_select=sub_select_cache; /* Patch previous */
4975
/* These init changes read_record */
4976
if (tab->use_quick == 2)
4978
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
4979
tab->read_first_record= join_init_quick_read_record;
4981
status_var_increment(join->session->status_var.select_range_check_count);
4985
tab->read_first_record= join_init_read_record;
4986
if (i == join->const_tables)
4988
if (tab->select && tab->select->quick)
4991
status_var_increment(join->session->status_var.select_range_count);
4995
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
4997
status_var_increment(join->session->status_var.select_scan_count);
5002
if (tab->select && tab->select->quick)
5005
status_var_increment(join->session->status_var.select_full_range_join_count);
5009
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
5011
status_var_increment(join->session->status_var.select_full_join_count);
5014
if (!table->no_keyread)
5016
if (tab->select && tab->select->quick &&
5017
tab->select->quick->index != MAX_KEY && //not index_merge
5018
table->covering_keys.test(tab->select->quick->index))
5021
table->cursor->extra(HA_EXTRA_KEYREAD);
5023
else if (!table->covering_keys.none() &&
5024
!(tab->select && tab->select->quick))
5025
{ // Only read index tree
5026
if (!tab->insideout_match_tab)
5029
See bug #26447: "Using the clustered index for a table scan
5030
is always faster than using a secondary index".
5032
if (table->s->primary_key != MAX_KEY &&
5033
table->cursor->primary_key_is_clustered())
5034
tab->index= table->s->primary_key;
5036
tab->index= table->find_shortest_key(&table->covering_keys);
5038
tab->read_first_record= join_read_first;
5039
tab->type= AM_NEXT; // Read with index_first / index_next
5051
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
5055
/** Update the dependency map for the tables. */
5056
static void update_depend_map(JOIN *join)
5058
JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
5060
for (; join_tab != end ; join_tab++)
5062
table_reference_st *ref= &join_tab->ref;
5063
table_map depend_map= 0;
5064
Item **item=ref->items;
5066
for (i=0 ; i < ref->key_parts ; i++,item++)
5067
depend_map|=(*item)->used_tables();
5068
ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;
5069
depend_map&= ~OUTER_REF_TABLE_BIT;
5070
for (JoinTable **tab=join->map2table; depend_map; tab++,depend_map>>=1 )
5073
ref->depend_map|=(*tab)->ref.depend_map;
5078
/** Update the dependency map for the sort order. */
5079
static void update_depend_map(JOIN *join, order_st *order)
5081
for (; order ; order=order->next)
5083
table_map depend_map;
5084
order->item[0]->update_used_tables();
5085
order->depend_map=depend_map=order->item[0]->used_tables();
5086
// Not item_sum(), RAND() and no reference to table outside of sub select
5087
if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))
5088
&& !order->item[0]->with_sum_func)
5090
for (JoinTable **tab=join->map2table; depend_map; tab++, depend_map>>=1)
5093
order->depend_map|=(*tab)->ref.depend_map;
5100
Remove all constants and check if order_st only contains simple
5103
simple_order is set to 1 if sort_order only uses fields from head table
5104
and the head table is not a LEFT JOIN table.
5106
@param join Join handler
5107
@param first_order List of SORT or GROUP order
5108
@param cond WHERE statement
5109
@param change_list Set to 1 if we should remove things from list.
5110
If this is not set, then only simple_order is
5112
@param simple_order Set to 1 if we are only using simple expressions
5115
Returns new sort order
5117
static order_st *remove_constants(JOIN *join,order_st *first_order, COND *cond, bool change_list, bool *simple_order)
5119
if (join->tables == join->const_tables)
5120
return change_list ? 0 : first_order; // No need to sort
5122
order_st *order,**prev_ptr;
5123
table_map first_table= join->join_tab[join->const_tables].table->map;
5124
table_map not_const_tables= ~join->const_table_map;
5127
prev_ptr= &first_order;
5128
*simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;
5130
/* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
5132
update_depend_map(join, first_order);
5133
for (order=first_order; order ; order=order->next)
5135
table_map order_tables=order->item[0]->used_tables();
5136
if (order->item[0]->with_sum_func)
5137
*simple_order=0; // Must do a temp table to sort
5138
else if (!(order_tables & not_const_tables))
5140
if (order->item[0]->with_subselect)
5141
order->item[0]->val_str(&order->item[0]->str_value);
5142
continue; // skip const item
5146
if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))
5151
if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
5155
if ((ref=order_tables & (not_const_tables ^ first_table)))
5157
if (!(order_tables & first_table) &&
5158
only_eq_ref_tables(join,first_order, ref))
5162
*simple_order=0; // Must do a temp table to sort
5167
*prev_ptr= order; // use this entry
5168
prev_ptr= &order->next;
5172
if (prev_ptr == &first_order) // Nothing to sort/group
5174
return(first_order);
5177
static int return_zero_rows(JOIN *join,
5178
select_result *result,
5182
uint64_t select_options,
5186
if (select_options & SELECT_DESCRIBE)
5188
optimizer::ExplainPlan planner(join,
5193
planner.printPlan();
5201
for (TableList *table= tables; table; table= table->next_leaf)
5202
table->table->mark_as_null_row(); // All fields are NULL
5203
if (having && having->val_int() == 0)
5206
if (! (result->send_fields(fields)))
5210
List_iterator_fast<Item> it(fields);
5212
while ((item= it++))
5213
item->no_rows_in_result();
5214
result->send_data(fields);
5216
result->send_eof(); // Should be safe
5218
/* Update results for FOUND_ROWS */
5219
join->session->limit_found_rows= join->session->examined_row_count= 0;
5224
Simplify joins replacing outer joins by inner joins whenever it's
5227
The function, during a retrieval of join_list, eliminates those
5228
outer joins that can be converted into inner join, possibly nested.
5229
It also moves the on expressions for the converted outer joins
5230
and from inner joins to conds.
5231
The function also calculates some attributes for nested joins:
5235
- on_expr_dep_tables
5236
The first two attributes are used to test whether an outer join can
5237
be substituted for an inner join. The third attribute represents the
5238
relation 'to be dependent on' for tables. If table t2 is dependent
5239
on table t1, then in any evaluated execution plan table access to
5240
table t2 must precede access to table t2. This relation is used also
5241
to check whether the query contains invalid cross-references.
5242
The forth attribute is an auxiliary one and is used to calculate
5244
As the attribute dep_tables qualifies possibles orders of tables in the
5245
execution plan, the dependencies required by the straight join
5246
modifiers are reflected in this attribute as well.
5247
The function also removes all braces that can be removed from the join
5248
expression without changing its meaning.
5251
An outer join can be replaced by an inner join if the where condition
5252
or the on expression for an embedding nested join contains a conjunctive
5253
predicate rejecting null values for some attribute of the inner tables.
5257
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5259
the predicate t2.b < 5 rejects nulls.
5260
The query is converted first to:
5262
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5264
then to the equivalent form:
5266
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
5270
Similarly the following query:
5272
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
5277
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
5281
One conversion might trigger another:
5283
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
5284
LEFT JOIN t3 ON t3.b=t2.b
5285
WHERE t3 IS NOT NULL =>
5286
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
5287
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
5288
SELECT * FROM t1, t2, t3
5289
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
5292
The function removes all unnecessary braces from the expression
5293
produced by the conversions.
5296
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5298
finally is converted to:
5300
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5305
It also will remove braces from the following queries:
5307
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
5308
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
5311
The benefit of this simplification procedure is that it might return
5312
a query for which the optimizer can evaluate execution plan with more
5313
join orders. With a left join operation the optimizer does not
5314
consider any plan where one of the inner tables is before some of outer
5318
The function is implemented by a recursive procedure. On the recursive
5319
ascent all attributes are calculated, all outer joins that can be
5320
converted are replaced and then all unnecessary braces are removed.
5321
As join list contains join tables in the reverse order sequential
5322
elimination of outer joins does not require extra recursive calls.
5325
Remove all semi-joins that have are within another semi-join (i.e. have
5326
an "ancestor" semi-join nest)
5329
Here is an example of a join query with invalid cross references:
5331
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
5334
@param join reference to the query info
5335
@param join_list list representation of the join to be converted
5336
@param conds conditions to add on expressions for converted joins
5337
@param top true <=> conds is the where condition
5340
- The new condition, if success
5343
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top)
5346
nested_join_st *nested_join;
5347
TableList *prev_table= 0;
5348
List_iterator<TableList> li(*join_list);
5351
Try to simplify join operations from join_list.
5352
The most outer join operation is checked for conversion first.
5354
while ((table= li++))
5356
table_map used_tables;
5357
table_map not_null_tables= (table_map) 0;
5359
if ((nested_join= table->nested_join))
5362
If the element of join_list is a nested join apply
5363
the procedure to its nested join list first.
5367
Item *expr= table->on_expr;
5369
If an on expression E is attached to the table,
5370
check all null rejected predicates in this expression.
5371
If such a predicate over an attribute belonging to
5372
an inner table of an embedded outer join is found,
5373
the outer join is converted to an inner join and
5374
the corresponding on expression is added to E.
5376
expr= simplify_joins(join, &nested_join->join_list, expr, false);
5378
if (!table->prep_on_expr || expr != table->on_expr)
5382
table->on_expr= expr;
5383
table->prep_on_expr= expr->copy_andor_structure(join->session);
5386
nested_join->used_tables= (table_map) 0;
5387
nested_join->not_null_tables=(table_map) 0;
5388
conds= simplify_joins(join, &nested_join->join_list, conds, top);
5389
used_tables= nested_join->used_tables;
5390
not_null_tables= nested_join->not_null_tables;
5394
if (!table->prep_on_expr)
5395
table->prep_on_expr= table->on_expr;
5396
used_tables= table->table->map;
5398
not_null_tables= conds->not_null_tables();
5401
if (table->embedding)
5403
table->embedding->nested_join->used_tables|= used_tables;
5404
table->embedding->nested_join->not_null_tables|= not_null_tables;
5407
if (!table->outer_join || (used_tables & not_null_tables))
5410
For some of the inner tables there are conjunctive predicates
5411
that reject nulls => the outer join can be replaced by an inner join.
5413
table->outer_join= 0;
5416
/* Add ON expression to the WHERE or upper-level ON condition. */
5419
conds= and_conds(conds, table->on_expr);
5420
conds->top_level_item();
5421
/* conds is always a new item as both cond and on_expr existed */
5422
assert(!conds->fixed);
5423
conds->fix_fields(join->session, &conds);
5426
conds= table->on_expr;
5427
table->prep_on_expr= table->on_expr= 0;
5435
Only inner tables of non-convertible outer joins
5436
remain with on_expr.
5440
table->dep_tables|= table->on_expr->used_tables();
5441
if (table->embedding)
5443
table->dep_tables&= ~table->embedding->nested_join->used_tables;
5445
Embedding table depends on tables used
5446
in embedded on expressions.
5448
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
5451
table->dep_tables&= ~table->table->map;
5456
/* The order of tables is reverse: prev_table follows table */
5457
if (prev_table->straight)
5458
prev_table->dep_tables|= used_tables;
5459
if (prev_table->on_expr)
5461
prev_table->dep_tables|= table->on_expr_dep_tables;
5462
table_map prev_used_tables= prev_table->nested_join ?
5463
prev_table->nested_join->used_tables :
5464
prev_table->table->map;
5466
If on expression contains only references to inner tables
5467
we still make the inner tables dependent on the outer tables.
5468
It would be enough to set dependency only on one outer table
5469
for them. Yet this is really a rare case.
5471
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5472
prev_table->dep_tables|= used_tables;
5479
Flatten nested joins that can be flattened.
5480
no ON expression and not a semi-join => can be flattened.
5483
while ((table= li++))
5485
nested_join= table->nested_join;
5486
if (nested_join && !table->on_expr)
5489
List_iterator<TableList> it(nested_join->join_list);
5492
tbl->embedding= table->embedding;
5493
tbl->join_list= table->join_list;
5495
li.replace(nested_join->join_list);
5501
static int remove_duplicates(JOIN *join, Table *entry,List<Item> &fields, Item *having)
5504
uint32_t reclength,offset;
5505
uint32_t field_count;
5506
Session *session= join->session;
5508
entry->reginfo.lock_type=TL_WRITE;
5510
/* Calculate how many saved fields there is in list */
5512
List_iterator<Item> it(fields);
5516
if (item->get_tmp_table_field() && ! item->const_item())
5520
if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)
5521
{ // only const items with no OPTION_FOUND_ROWS
5522
join->unit->select_limit_cnt= 1; // Only send first row
5525
Field **first_field=entry->field+entry->s->fields - field_count;
5526
offset= (field_count ?
5527
entry->field[entry->s->fields - field_count]->
5528
offset(entry->record[0]) : 0);
5529
reclength= entry->s->reclength-offset;
5531
entry->free_io_cache(); // Safety
5532
entry->cursor->info(HA_STATUS_VARIABLE);
5533
if (entry->s->db_type() == heap_engine ||
5534
(!entry->s->blob_fields &&
5535
((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->cursor->stats.records <
5536
session->variables.sortbuff_size)))
5537
error= remove_dup_with_hash_index(join->session, entry,
5538
field_count, first_field,
5541
error= remove_dup_with_compare(join->session, entry, first_field, offset,
5544
free_blobs(first_field);
5549
Function to setup clauses without sum functions.
5551
static int setup_without_group(Session *session,
5552
Item **ref_pointer_array,
5556
List<Item> &all_fields,
5560
bool *hidden_group_fields)
5563
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
5565
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5566
res= session->setup_conds(tables, conds);
5568
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
5569
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
5571
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5572
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
5573
group, hidden_group_fields);
5574
session->lex->allow_sum_func= save_allow_sum_func;
5579
Calculate the best possible join and initialize the join structure.
5586
static bool make_join_statistics(JOIN *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5591
uint32_t table_count;
5592
uint32_t const_count;
5594
table_map found_const_table_map;
5595
table_map all_table_map;
5596
table_map found_ref;
5600
Table **table_vector= NULL;
5601
JoinTable *stat= NULL;
5602
JoinTable *stat_end= NULL;
5604
JoinTable **stat_ref= NULL;
5605
optimizer::KeyUse *keyuse= NULL;
5606
optimizer::KeyUse *start_keyuse= NULL;
5607
table_map outer_join= 0;
5608
vector<optimizer::SargableParam> sargables;
5609
JoinTable *stat_vector[MAX_TABLES+1];
5610
optimizer::Position *partial_pos;
5612
table_count= join->tables;
5613
stat= (JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
5614
stat_ref= (JoinTable**) join->session->alloc(sizeof(JoinTable*)*MAX_TABLES);
5615
table_vector= (Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
5616
if (! stat || ! stat_ref || ! table_vector)
5619
join->best_ref=stat_vector;
5621
stat_end=stat+table_count;
5622
found_const_table_map= all_table_map=0;
5627
s++, tables= tables->next_leaf, i++)
5629
TableList *embedding= tables->embedding;
5632
s->const_keys.reset();
5633
s->checked_keys.reset();
5634
s->needed_reg.reset();
5635
table_vector[i]=s->table=table=tables->table;
5636
table->pos_in_table_list= tables;
5637
error= table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5640
table->print_error(error, MYF(0));
5643
table->quick_keys.reset();
5644
table->reginfo.join_tab=s;
5645
table->reginfo.not_exists_optimize=0;
5646
memset(table->const_key_parts, 0,
5647
sizeof(key_part_map)*table->s->keys);
5648
all_table_map|= table->map;
5650
s->info=0; // For describe
5652
s->dependent= tables->dep_tables;
5653
s->key_dependent= 0;
5654
table->quick_condition_rows= table->cursor->stats.records;
5656
s->on_expr_ref= &tables->on_expr;
5657
if (*s->on_expr_ref)
5659
/* s is the only inner table of an outer join */
5660
if (!table->cursor->stats.records && !embedding)
5662
s->dependent= 0; // Ignore LEFT JOIN depend.
5663
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5666
outer_join|= table->map;
5667
s->embedding_map.reset();
5668
for (;embedding; embedding= embedding->embedding)
5669
s->embedding_map|= embedding->nested_join->nj_map;
5672
if (embedding && !(false && ! embedding->embedding))
5674
/* s belongs to a nested join, maybe to several embedded joins */
5675
s->embedding_map.reset();
5678
nested_join_st *nested_join= embedding->nested_join;
5679
s->embedding_map|= nested_join->nj_map;
5680
s->dependent|= embedding->dep_tables;
5681
embedding= embedding->embedding;
5682
outer_join|= nested_join->used_tables;
5687
if ((table->cursor->stats.records <= 1) && !s->dependent &&
5688
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5689
!join->no_const_tables)
5691
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5695
join->outer_join=outer_join;
5697
if (join->outer_join)
5700
Build transitive closure for relation 'to be dependent on'.
5701
This will speed up the plan search for many cases with outer joins,
5702
as well as allow us to catch illegal cross references/
5703
Warshall's algorithm is used to build the transitive closure.
5704
As we use bitmaps to represent the relation the complexity
5705
of the algorithm is O((number of tables)^2).
5707
for (i= 0, s= stat ; i < table_count ; i++, s++)
5709
for (uint32_t j= 0 ; j < table_count ; j++)
5711
table= stat[j].table;
5712
if (s->dependent & table->map)
5713
s->dependent |= table->reginfo.join_tab->dependent;
5716
s->table->maybe_null= 1;
5718
/* Catch illegal cross references for outer joins */
5719
for (i= 0, s= stat ; i < table_count ; i++, s++)
5721
if (s->dependent & s->table->map)
5723
join->tables=0; // Don't use join->table
5724
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
5727
s->key_dependent= s->dependent;
5731
if (conds || outer_join)
5732
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
5733
conds, join->cond_equal,
5734
~outer_join, join->select_lex, sargables))
5737
/* Read tables with 0 or 1 rows (system tables) */
5738
join->const_table_map= 0;
5740
optimizer::Position *p_pos= join->getFirstPosInPartialPlan();
5741
optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5742
while (p_pos < p_end)
5745
s= p_pos->getJoinTable();
5747
join->const_table_map|=s->table->map;
5748
if ((tmp= join_read_const_table(s, p_pos)))
5751
return 1; // Fatal error
5754
found_const_table_map|= s->table->map;
5758
/* loop until no more const tables are found */
5762
more_const_tables_found:
5767
We only have to loop from stat_vector + const_count as
5768
set_position() will move all const_tables first in stat_vector
5771
for (JoinTable **pos= stat_vector+const_count; (s= *pos); pos++)
5776
If equi-join condition by a key is null rejecting and after a
5777
substitution of a const table the key value happens to be null
5778
then we can state that there are no matches for this equi-join.
5780
if ((keyuse= s->keyuse) && *s->on_expr_ref && s->embedding_map.none())
5783
When performing an outer join operation if there are no matching rows
5784
for the single row of the outer table all the inner tables are to be
5785
null complemented and thus considered as constant tables.
5786
Here we apply this consideration to the case of outer join operations
5787
with a single inner table only because the case with nested tables
5788
would require a more thorough analysis.
5789
TODO. Apply single row substitution to null complemented inner tables
5790
for nested outer join operations.
5792
while (keyuse->getTable() == table)
5794
if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&
5795
keyuse->getVal()->is_null() && keyuse->isNullRejected())
5798
table->mark_as_null_row();
5799
found_const_table_map|= table->map;
5800
join->const_table_map|= table->map;
5801
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5802
goto more_const_tables_found;
5808
if (s->dependent) // If dependent on some table
5810
// All dep. must be constants
5811
if (s->dependent & ~(found_const_table_map))
5813
if (table->cursor->stats.records <= 1L &&
5814
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5815
!table->pos_in_table_list->embedding)
5819
join->const_table_map|=table->map;
5820
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5821
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5822
if ((tmp= join_read_const_table(s, partial_pos)))
5825
return 1; // Fatal error
5828
found_const_table_map|= table->map;
5832
/* check if table can be read by key or table only uses const refs */
5833
if ((keyuse=s->keyuse))
5836
while (keyuse->getTable() == table)
5838
start_keyuse= keyuse;
5839
key= keyuse->getKey();
5840
s->keys.set(key); // QQ: remove this ?
5847
if (keyuse->getVal()->type() != Item::NULL_ITEM &&
5848
! keyuse->getOptimizeFlags())
5850
if (! ((~found_const_table_map) & keyuse->getUsedTables()))
5851
const_ref.set(keyuse->getKeypart());
5853
refs|= keyuse->getUsedTables();
5854
eq_part.set(keyuse->getKeypart());
5857
} while (keyuse->getTable() == table && keyuse->getKey() == key);
5859
if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
5860
! table->pos_in_table_list->embedding)
5862
if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
5864
if (const_ref == eq_part)
5865
{ // Found everything for ref.
5869
join->const_table_map|= table->map;
5870
set_position(join, const_count++, s, start_keyuse);
5871
if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
5873
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5874
if ((tmp=join_read_const_table(s, partial_pos)))
5877
return 1; // Fatal error
5880
found_const_table_map|= table->map;
5884
found_ref|= refs; // Table is const if all refs are const
5886
else if (const_ref == eq_part)
5887
s->const_keys.set(key);
5892
} while (join->const_table_map & found_ref && ref_changed);
5895
Update info on indexes that can be used for search lookups as
5896
reading const tables may has added new sargable predicates.
5898
if (const_count && ! sargables.empty())
5900
vector<optimizer::SargableParam>::iterator iter= sargables.begin();
5901
while (iter != sargables.end())
5903
Field *field= (*iter).getField();
5904
JoinTable *join_tab= field->table->reginfo.join_tab;
5905
key_map possible_keys= field->key_start;
5906
possible_keys&= field->table->keys_in_use_for_query;
5907
bool is_const= true;
5908
for (uint32_t j= 0; j < (*iter).getNumValues(); j++)
5909
is_const&= (*iter).isConstItem(j);
5911
join_tab[0].const_keys|= possible_keys;
5916
/* Calc how many (possible) matched records in each table */
5918
for (s=stat ; s < stat_end ; s++)
5920
if (s->type == AM_SYSTEM || s->type == AM_CONST)
5922
/* Only one matching row */
5923
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
5926
/* Approximate found rows and time to read them */
5927
s->found_records=s->records=s->table->cursor->stats.records;
5928
s->read_time=(ha_rows) s->table->cursor->scan_time();
5931
Set a max range of how many seeks we can expect when using keys
5932
This is can't be to high as otherwise we are likely to use
5935
s->worst_seeks= min((double) s->found_records / 10,
5936
(double) s->read_time*3);
5937
if (s->worst_seeks < 2.0) // Fix for small tables
5941
Add to stat->const_keys those indexes for which all group fields or
5942
all select distinct fields participate in one index.
5944
add_group_and_distinct_keys(join, s);
5946
if (s->const_keys.any() &&
5947
!s->table->pos_in_table_list->embedding)
5950
optimizer::SqlSelect *select= NULL;
5951
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);
5954
records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
5955
s->quick=select->quick;
5956
s->needed_reg=select->needed_reg;
5958
if (records == 0 && s->table->reginfo.impossible_range)
5961
Impossible WHERE or ON expression
5962
In case of ON, we mark that the we match one empty NULL row.
5963
In case of WHERE, don't set found_const_table_map to get the
5964
caller to abort with a zero row result.
5966
join->const_table_map|= s->table->map;
5967
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5969
if (*s->on_expr_ref)
5971
/* Generate empty row */
5972
s->info= "Impossible ON condition";
5973
found_const_table_map|= s->table->map;
5975
s->table->mark_as_null_row(); // All fields are NULL
5978
if (records != HA_POS_ERROR)
5980
s->found_records=records;
5981
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
5987
join->join_tab=stat;
5988
join->map2table=stat_ref;
5989
join->table= join->all_tables=table_vector;
5990
join->const_tables=const_count;
5991
join->found_const_table_map=found_const_table_map;
5993
/* Find an optimal join order of the non-constant tables. */
5994
if (join->const_tables != join->tables)
5996
optimize_keyuse(join, keyuse_array);
5997
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->query, join->session->thread_id);
5998
bool res= choose_plan(join, all_table_map & ~join->const_table_map);
5999
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);
6005
join->copyPartialPlanIntoOptimalPlan(join->const_tables);
6006
join->best_read= 1.0;
6008
/* Generate an execution plan from the found optimal join order. */
6009
return (join->session->killed || get_best_combination(join));
6013
Assign each nested join structure a bit in the nested join bitset.
6015
Assign each nested join structure (except "confluent" ones - those that
6016
embed only one element) a bit in the nested join bitset.
6018
@param join Join being processed
6019
@param join_list List of tables
6020
@param first_unused Number of first unused bit in the nest joing bitset before the
6024
This function is called after simplify_joins(), when there are no
6025
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
6026
we will not run out of bits in the nested join bitset.
6029
First unused bit in the nest join bitset after the call.
6031
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
6033
List_iterator<TableList> li(*join_list);
6035
while ((table= li++))
6037
nested_join_st *nested_join;
6038
if ((nested_join= table->nested_join))
6041
It is guaranteed by simplify_joins() function that a nested join
6042
that has only one child is either
6043
- a single-table view (the child is the underlying table), or
6044
- a single-table semi-join nest
6046
We don't assign bits to such sj-nests because
6047
1. it is redundant (a "sequence" of one table cannot be interleaved
6049
2. we could run out of bits in the nested join bitset otherwise.
6051
if (nested_join->join_list.elements != 1)
6053
/* Don't assign bits to sj-nests */
6055
nested_join->nj_map.set(first_unused++);
6056
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
6061
return(first_unused);
6066
Return table number if there is only one table in sort order
6067
and group and order is compatible, else return 0.
6069
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables)
6071
table_map map= (table_map) 0;
6074
a= b; // Only one need to be given
6078
for (; a && b; a=a->next,b=b->next)
6080
if (!(*a->item)->eq(*b->item,1))
6081
return (Table *) NULL;
6082
map|= a->item[0]->used_tables();
6084
if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
6085
return (Table *) NULL;
6087
for (; !(map & tables->table->map); tables= tables->next_leaf) {};
6088
if (map != tables->table->map)
6089
return (Table *) NULL; // More than one table
6090
return tables->table;
6094
Set nested_join_st::counter=0 in all nested joins in passed list.
6096
Recursively set nested_join_st::counter=0 for all nested joins contained in
6097
the passed join_list.
6099
@param join_list List of nested joins to process. It may also contain base
6100
tables which will be ignored.
6102
static void reset_nj_counters(List<TableList> *join_list)
6104
List_iterator<TableList> li(*join_list);
6106
while ((table= li++))
6108
nested_join_st *nested_join;
6109
if ((nested_join= table->nested_join))
6111
nested_join->counter_= 0;
6112
reset_nj_counters(&nested_join->join_list);
6119
Return 1 if second is a subpart of first argument.
6121
If first parts has different direction, change it to second part
6122
(group is sorted like order)
6124
static bool test_if_subpart(order_st *a,order_st *b)
6126
for (; a && b; a=a->next,b=b->next)
6128
if ((*a->item)->eq(*b->item,1))
6137
Nested joins perspective: Remove the last table from the join order.
6139
Remove the last table from the partial join order and update the nested
6140
joins counters and join->cur_embedding_map. It is ok to call this
6141
function for the first table in join order (for which
6142
check_interleaving_with_nj has not been called)
6144
@param last join table to remove, it is assumed to be the last in current
6147
static void restore_prev_nj_state(JoinTable *last)
6149
TableList *last_emb= last->table->pos_in_table_list->embedding;
6150
JOIN *join= last->join;
6153
if (last_emb->on_expr)
6155
if (!(--last_emb->nested_join->counter_))
6156
join->cur_embedding_map&= ~last_emb->nested_join->nj_map;
6157
else if (last_emb->nested_join->join_list.elements-1 ==
6158
last_emb->nested_join->counter_)
6159
join->cur_embedding_map|= last_emb->nested_join->nj_map;
6163
last_emb= last_emb->embedding;
6168
Determine if the set is already ordered for order_st BY, so it can
6169
disable join cache because it will change the ordering of the results.
6170
Code handles sort table that is at any location (not only first after
6171
the const tables) despite the fact that it's currently prohibited.
6172
We must disable join cache if the first non-const table alone is
6173
ordered. If there is a temp table the ordering is done as a last
6174
operation and doesn't prevent join cache usage.
6176
static uint32_t make_join_orderinfo(JOIN *join)
6180
return join->tables;
6182
for (i=join->const_tables ; i < join->tables ; i++)
6184
JoinTable *tab= join->join_tab+i;
6185
Table *table= tab->table;
6186
if ((table == join->sort_by_table &&
6187
(!join->order || join->skip_sort_order)) ||
6188
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
6197
Create a condition for a const reference and add this to the
6198
currenct select for the table.
6200
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)
6202
if (!join_tab->ref.key_parts)
6205
Item_cond_and *cond=new Item_cond_and();
6206
Table *table=join_tab->table;
6211
for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6213
Field *field=table->field[table->key_info[join_tab->ref.key].key_part[i].
6215
Item *value=join_tab->ref.items[i];
6216
cond->add(new Item_func_equal(new Item_field(field), value));
6218
if (session->is_fatal_error)
6222
cond->fix_fields(session, (Item**)&cond);
6223
if (join_tab->select)
6225
error=(int) cond->add(join_tab->select->cond);
6226
join_tab->select_cond=join_tab->select->cond=cond;
6228
else if ((join_tab->select= optimizer::make_select(join_tab->table, 0, 0, cond, 0,
6230
join_tab->select_cond=cond;
6232
return(error ? true : false);
6235
static void free_blobs(Field **ptr)
6237
for (; *ptr ; ptr++)
6239
if ((*ptr)->flags & BLOB_FLAG)
6240
((Field_blob *) (*ptr))->free();
6245
@} (end of group Query_Optimizer)
added
removed
drizzled/join.cc
