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"
67
extern plugin::StorageEngine *heap_engine;
68
extern std::bitset<12> test_flags;
70
/** Declarations of static functions used in this source file. */
71
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
72
static void calc_group_buffer(JOIN *join,order_st *group);
73
static bool alloc_group_fields(JOIN *join,order_st *group);
74
static uint32_t cache_record_length(JOIN *join, uint32_t index);
75
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
76
static bool get_best_combination(JOIN *join);
77
static void set_position(JOIN *join,
80
optimizer::KeyUse *key);
81
static bool choose_plan(JOIN *join,table_map join_tables);
82
static void best_access_path(JOIN *join, JoinTable *s,
84
table_map remaining_tables,
88
static void optimize_straight_join(JOIN *join, table_map join_tables);
89
static bool greedy_search(JOIN *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
90
static bool best_extension_by_limited_search(JOIN *join,
91
table_map remaining_tables,
96
uint32_t prune_level);
97
static uint32_t determine_search_depth(JOIN* join);
98
static bool make_simple_join(JOIN *join,Table *tmp_table);
99
static void make_outerjoin_info(JOIN *join);
100
static bool make_join_select(JOIN *join, optimizer::SqlSelect *select,COND *item);
101
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
102
static void update_depend_map(JOIN *join);
103
static void update_depend_map(JOIN *join, order_st *order);
104
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond, bool change_list, bool *simple_order);
105
static int return_zero_rows(JOIN *join,
110
uint64_t select_options,
113
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top);
114
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields, Item *having);
115
static int setup_without_group(Session *session,
116
Item **ref_pointer_array,
120
List<Item> &all_fields,
124
bool *hidden_group_fields);
125
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
126
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
127
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
128
static void reset_nj_counters(List<TableList> *join_list);
129
static bool test_if_subpart(order_st *a,order_st *b);
130
static void restore_prev_nj_state(JoinTable *last);
131
static uint32_t make_join_orderinfo(JOIN *join);
132
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
133
static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
136
Prepare of whole select (including sub queries in future).
139
Add check of calculation of GROUP functions and fields:
140
SELECT COUNT(*)+table.col1 from table1;
147
int JOIN::prepare(Item ***rref_pointer_array,
148
TableList *tables_init,
152
order_st *order_init,
153
order_st *group_init,
155
Select_Lex *select_lex_arg,
156
Select_Lex_Unit *unit_arg)
158
// to prevent double initialization on EXPLAIN
164
group_list= group_init;
166
tables_list= tables_init;
167
select_lex= select_lex_arg;
168
select_lex->join= this;
169
join_list= &select_lex->top_join_list;
170
union_part= unit_arg->is_union();
172
session->lex->current_select->is_item_list_lookup= 1;
174
If we have already executed SELECT, then it have not sense to prevent
175
its table from update (see unique_table())
177
if (session->derived_tables_processing)
178
select_lex->exclude_from_table_unique_test= true;
180
/* Check that all tables, fields, conds and order are ok */
182
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
183
setup_tables_and_check_access(session, &select_lex->context, join_list,
184
tables_list, &select_lex->leaf_tables,
188
TableList *table_ptr;
189
for (table_ptr= select_lex->leaf_tables;
191
table_ptr= table_ptr->next_leaf)
194
if (setup_wild(session, fields_list, &all_fields, wild_num) ||
195
select_lex->setup_ref_array(session, og_num) ||
196
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
198
setup_without_group(session, (*rref_pointer_array), tables_list,
199
select_lex->leaf_tables, fields_list,
200
all_fields, &conds, order, group_list,
201
&hidden_group_fields))
204
ref_pointer_array= *rref_pointer_array;
208
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
209
session->where="having clause";
210
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
211
select_lex->having_fix_field= 1;
212
bool having_fix_rc= (!having->fixed &&
213
(having->fix_fields(session, &having) ||
214
having->check_cols(1)));
215
select_lex->having_fix_field= 0;
216
if (having_fix_rc || session->is_error())
218
session->lex->allow_sum_func= save_allow_sum_func;
222
Item_subselect *subselect;
223
Item_in_subselect *in_subs= NULL;
225
Are we in a subquery predicate?
226
TODO: the block below will be executed for every PS execution without need.
228
if ((subselect= select_lex->master_unit()->item))
230
if (subselect->substype() == Item_subselect::IN_SUBS)
231
in_subs= (Item_in_subselect*)subselect;
234
bool do_materialize= true;
236
Check if the subquery predicate can be executed via materialization.
237
The required conditions are:
238
1. Subquery predicate is an IN/=ANY subq predicate
239
2. Subquery is a single SELECT (not a UNION)
240
3. Subquery is not a table-less query. In this case there is no
241
point in materializing.
242
4. Subquery predicate is a top-level predicate
243
(this implies it is not negated)
244
TODO: this is a limitation that should be lifeted once we
245
implement correct NULL semantics (WL#3830)
246
5. Subquery is non-correlated
248
This is an overly restrictive condition. It can be extended to:
249
(Subquery is non-correlated ||
250
Subquery is correlated to any query outer to IN predicate ||
251
(Subquery is correlated to the immediate outer query &&
252
Subquery !contains {GROUP BY, ORDER BY [LIMIT],
253
aggregate functions) && subquery predicate is not under "NOT IN"))
254
6. No execution method was already chosen (by a prepared statement).
256
(*) The subquery must be part of a SELECT statement. The current
257
condition also excludes multi-table update statements.
259
We have to determine whether we will perform subquery materialization
260
before calling the IN=>EXISTS transformation, so that we know whether to
261
perform the whole transformation or only that part of it which wraps
262
Item_in_subselect in an Item_in_optimizer.
264
if (do_materialize &&
266
!select_lex->master_unit()->first_select()->next_select() && // 2
267
select_lex->master_unit()->first_select()->leaf_tables && // 3
268
session->lex->sql_command == SQLCOM_SELECT) // *
270
if (in_subs->is_top_level_item() && // 4
271
!in_subs->is_correlated && // 5
272
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
273
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
276
Item_subselect::trans_res trans_res;
277
if ((trans_res= subselect->select_transformer(this)) !=
278
Item_subselect::RES_OK)
280
return((trans_res == Item_subselect::RES_ERROR));
289
for (ord= order; ord; ord= ord->next)
291
Item *item= *ord->item;
292
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
293
item->split_sum_func(session, ref_pointer_array, all_fields);
297
if (having && having->with_sum_func)
298
having->split_sum_func(session, ref_pointer_array, all_fields,
300
if (select_lex->inner_sum_func_list)
302
Item_sum *end=select_lex->inner_sum_func_list;
303
Item_sum *item_sum= end;
306
item_sum= item_sum->next;
307
item_sum->split_sum_func(session, ref_pointer_array,
308
all_fields, item_sum->ref_by, false);
309
} while (item_sum != end);
312
if (select_lex->inner_refs_list.elements &&
313
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
317
Check if there are references to un-aggregated columns when computing
318
aggregate functions with implicit grouping (there is no GROUP BY).
320
MODE_ONLY_FULL_GROUP_BY is enabled here by default
323
select_lex->full_group_by_flag.test(NON_AGG_FIELD_USED) &&
324
select_lex->full_group_by_flag.test(SUM_FUNC_USED))
326
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
327
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
331
/* Caclulate the number of groups */
333
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
341
* The below will create the new table for
342
* CREATE TABLE ... SELECT
344
* @see create_table_from_items() in drizzled/sql_insert.cc
346
if (result && result->prepare(fields_list, unit_arg))
349
/* Init join struct */
350
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
351
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
352
this->group= group_list != 0;
355
#ifdef RESTRICTED_GROUP
356
if (sum_func_count && !group_list && (func_count || field_count))
358
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
362
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
364
if (alloc_func_list())
374
Remove the predicates pushed down into the subquery
377
JOIN::remove_subq_pushed_predicates()
378
where IN Must be NULL
379
OUT The remaining WHERE condition, or NULL
382
Given that this join will be executed using (unique|index)_subquery,
383
without "checking NULL", remove the predicates that were pushed down
386
If the subquery compares scalar values, we can remove the condition that
387
was wrapped into trig_cond (it will be checked when needed by the subquery
390
If the subquery compares row values, we need to keep the wrapped
391
equalities in the WHERE clause: when the left (outer) tuple has both NULL
392
and non-NULL values, we'll do a full table scan and will rely on the
393
equalities corresponding to non-NULL parts of left tuple to filter out
394
non-matching records.
396
TODO: We can remove the equalities that will be guaranteed to be true by the
397
fact that subquery engine will be using index lookup. This must be done only
398
for cases where there are no conversion errors of significance, e.g. 257
399
that is searched in a byte. But this requires homogenization of the return
400
codes of all Field*::store() methods.
402
void JOIN::remove_subq_pushed_predicates(Item **where)
404
if (conds->type() == Item::FUNC_ITEM &&
405
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
406
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
407
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
408
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
409
((Item_func *)conds)->arguments()[0]))
417
global select optimisation.
420
error code saved in field 'error'
429
// to prevent double initialization on EXPLAIN
434
session->set_proc_info("optimizing");
435
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
436
unit->select_limit_cnt);
437
/* select_limit is used to decide if we are likely to scan the whole table */
438
select_limit= unit->select_limit_cnt;
439
if (having || (select_options & OPTION_FOUND_ROWS))
440
select_limit= HA_POS_ERROR;
441
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
442
// Ignore errors of execution if option IGNORE present
443
if (session->lex->ignore)
444
session->lex->current_select->no_error= 1;
446
#ifdef HAVE_REF_TO_FIELDS // Not done yet
447
/* Add HAVING to WHERE if possible */
448
if (having && !group_list && !sum_func_count)
455
else if ((conds=new Item_cond_and(conds,having)))
458
Item_cond_and can't be fixed after creation, so we do not check
461
conds->fix_fields(session, &conds);
462
conds->change_ref_to_fields(session, tables_list);
463
conds->top_level_item();
469
/* Convert all outer joins to inner joins if possible */
470
conds= simplify_joins(this, join_list, conds, true);
471
build_bitmap_for_nested_joins(join_list, 0);
473
conds= optimize_cond(this, conds, join_list, &cond_value);
474
if (session->is_error())
481
having= optimize_cond(this, having, join_list, &having_value);
482
if (session->is_error())
487
if (select_lex->where)
488
select_lex->cond_value= cond_value;
489
if (select_lex->having)
490
select_lex->having_value= having_value;
492
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
493
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
494
{ /* Impossible cond */
495
zero_result_cause= having_value == Item::COND_FALSE ?
496
"Impossible HAVING" : "Impossible WHERE";
502
/* Optimize count(*), cmin() and cmax() */
503
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
507
optimizer::sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
508
to the WHERE conditions,
509
or 1 if all items were resolved,
510
or 0, or an error number HA_ERR_...
512
if ((res= optimizer::sum_query(select_lex->leaf_tables, all_fields, conds)))
514
if (res == HA_ERR_KEY_NOT_FOUND)
516
zero_result_cause= "No matching min/max row";
527
zero_result_cause= "No matching min/max row";
531
zero_result_cause= "Select tables optimized away";
532
tables_list= 0; // All tables resolved
534
Extract all table-independent conditions and replace the WHERE
535
clause with them. All other conditions were computed by optimizer::sum_query
536
and the MIN/MAX/COUNT function(s) have been replaced by constants,
537
so there is no need to compute the whole WHERE clause again.
538
Notice that make_cond_for_table() will always succeed to remove all
539
computed conditions, because optimizer::sum_query() is applicable only to
541
Preserve conditions for EXPLAIN.
543
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
545
COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
546
conds= table_independent_conds;
555
error= -1; // Error is sent to client
556
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
558
/* Calculate how to do the join */
559
session->set_proc_info("statistics");
560
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
561
session->is_fatal_error)
566
/* Remove distinct if only const tables */
567
select_distinct= select_distinct && (const_tables != tables);
568
session->set_proc_info("preparing");
569
if (result->initialize_tables(this))
571
return 1; // error == -1
573
if (const_table_map != found_const_table_map &&
574
!(select_options & SELECT_DESCRIBE) &&
576
!(conds->used_tables() & RAND_TABLE_BIT) ||
577
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
579
zero_result_cause= "no matching row in const table";
583
if (!(session->options & OPTION_BIG_SELECTS) &&
584
best_read > (double) session->variables.max_join_size &&
585
!(select_options & SELECT_DESCRIBE))
587
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
591
if (const_tables && !(select_options & SELECT_NO_UNLOCK))
592
mysql_unlock_some_tables(session, table, const_tables);
593
if (!conds && outer_join)
595
/* Handle the case where we have an OUTER JOIN without a WHERE */
596
conds=new Item_int((int64_t) 1,1); // Always true
598
select= optimizer::make_select(*table, const_table_map,
599
const_table_map, conds, 1, &error);
606
reset_nj_counters(join_list);
607
make_outerjoin_info(this);
610
Among the equal fields belonging to the same multiple equality
611
choose the one that is to be retrieved first and substitute
612
all references to these in where condition for a reference for
617
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
618
conds->update_used_tables();
622
Permorm the the optimization on fields evaluation mentioned above
623
for all on expressions.
625
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
627
if (*tab->on_expr_ref)
629
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
632
(*tab->on_expr_ref)->update_used_tables();
636
if (conds &&!outer_join && const_table_map != found_const_table_map &&
637
(select_options & SELECT_DESCRIBE) &&
638
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
640
conds=new Item_int((int64_t) 0,1); // Always false
643
if (make_join_select(this, select, conds))
646
"Impossible WHERE noticed after reading const tables";
647
return(0); // error == 0
650
error= -1; /* if goto err */
652
/* Optimize distinct away if possible */
654
order_st *org_order= order;
655
order= remove_constants(this, order,conds,1, &simple_order);
656
if (session->is_error())
663
If we are using ORDER BY NULL or ORDER BY const_expression,
664
return result in any order (even if we are using a GROUP BY)
666
if (!order && org_order)
670
Check if we can optimize away GROUP BY/DISTINCT.
671
We can do that if there are no aggregate functions, the
672
fields in DISTINCT clause (if present) and/or columns in GROUP BY
673
(if present) contain direct references to all key parts of
674
an unique index (in whatever order) and if the key parts of the
675
unique index cannot contain NULLs.
676
Note that the unique keys for DISTINCT and GROUP BY should not
677
be the same (as long as they are unique).
679
The FROM clause must contain a single non-constant table.
681
if (tables - const_tables == 1 && (group_list || select_distinct) &&
682
! tmp_table_param.sum_func_count &&
683
(! join_tab[const_tables].select ||
684
! join_tab[const_tables].select->quick ||
685
join_tab[const_tables].select->quick->get_type() !=
686
optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))
688
if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
691
We have found that grouping can be removed since groups correspond to
692
only one row anyway, but we still have to guarantee correct result
693
order. The line below effectively rewrites the query from GROUP BY
694
<fields> to ORDER BY <fields>. There are two exceptions:
695
- if skip_sort_order is set (see above), then we can simply skip
697
- we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'
698
with the GROUP BY ones, i.e. either one is a prefix of another.
699
We only check if the ORDER BY is a prefix of GROUP BY. In this case
700
test_if_subpart() copies the ASC/DESC attributes from the original
702
If GROUP BY is a prefix of order_st BY, then it is safe to leave
705
if (! order || test_if_subpart(group_list, order))
706
order= skip_sort_order ? 0 : group_list;
708
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
709
rewritten to IGNORE INDEX FOR order_st BY(fields).
711
join_tab->table->keys_in_use_for_order_by=
712
join_tab->table->keys_in_use_for_group_by;
716
if (select_distinct &&
717
list_contains_unique_index(join_tab[const_tables].table,
718
find_field_in_item_list,
719
(void *) &fields_list))
724
if (group_list || tmp_table_param.sum_func_count)
726
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
729
else if (select_distinct && tables - const_tables == 1)
732
We are only using one table. In this case we change DISTINCT to a
734
- The GROUP BY can be done through indexes (no sort) and the order_st
735
BY only uses selected fields.
736
(In this case we can later optimize away GROUP BY and order_st BY)
737
- We are scanning the whole table without LIMIT
739
- We are using CALC_FOUND_ROWS
740
- We are using an ORDER BY that can't be optimized away.
742
We don't want to use this optimization when we are using LIMIT
743
because in this case we can just create a temporary table that
744
holds LIMIT rows and stop when this table is full.
746
JoinTable *tab= &join_tab[const_tables];
747
bool all_order_fields_used;
749
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
750
&tab->table->keys_in_use_for_order_by);
751
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
752
order, fields_list, all_fields,
753
&all_order_fields_used)))
755
bool skip_group= (skip_sort_order &&
756
test_if_skip_sort_order(tab, group_list, select_limit, 1,
757
&tab->table->keys_in_use_for_group_by) != 0);
758
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
759
if ((skip_group && all_order_fields_used) ||
760
select_limit == HA_POS_ERROR ||
761
(order && !skip_sort_order))
763
/* Change DISTINCT to GROUP BY */
766
if (all_order_fields_used)
768
if (order && skip_sort_order)
771
Force MySQL to read the table in sorted order to get result in
774
tmp_table_param.quick_group=0;
778
group=1; // For end_write_group
783
else if (session->is_fatal_error) // End of memory
788
order_st *old_group_list;
789
group_list= remove_constants(this, (old_group_list= group_list), conds,
790
rollup.state == ROLLUP::STATE_NONE,
792
if (session->is_error())
797
if (old_group_list && !group_list)
800
if (!group_list && group)
802
order=0; // The output has only one row
804
select_distinct= 0; // No need in distinct for 1 row
805
group_optimized_away= 1;
808
calc_group_buffer(this, group_list);
809
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
811
if (test_if_subpart(group_list, order) ||
812
(!group_list && tmp_table_param.sum_func_count))
815
// Can't use sort on head table if using row cache
825
Check if we need to create a temporary table.
826
This has to be done if all tables are not already read (const tables)
827
and one of the following conditions holds:
828
- We are using DISTINCT (simple distinct's are already optimized away)
829
- We are using an ORDER BY or GROUP BY on fields not in the first table
830
- We are using different ORDER BY and GROUP BY orders
831
- The user wants us to buffer the result.
833
need_tmp= (const_tables != tables &&
834
((select_distinct || !simple_order || !simple_group) ||
835
(group_list && order) ||
836
test(select_options & OPTION_BUFFER_RESULT)));
838
uint32_t no_jbuf_after= make_join_orderinfo(this);
839
uint64_t select_opts_for_readinfo=
840
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
842
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
843
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
846
/* Create all structures needed for materialized subquery execution. */
847
if (setup_subquery_materialization())
850
/* Cache constant expressions in WHERE, HAVING, ON clauses. */
854
is this simple IN subquery?
856
if (!group_list && !order &&
857
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
858
tables == 1 && conds &&
864
if (join_tab[0].type == AM_EQ_REF && join_tab[0].ref.items[0]->name == in_left_expr_name)
866
remove_subq_pushed_predicates(&where);
867
save_index_subquery_explain_info(join_tab, where);
868
join_tab[0].type= AM_UNIQUE_SUBQUERY;
872
subselect_uniquesubquery_engine(session,
877
else if (join_tab[0].type == AM_REF &&
878
join_tab[0].ref.items[0]->name == in_left_expr_name)
880
remove_subq_pushed_predicates(&where);
881
save_index_subquery_explain_info(join_tab, where);
882
join_tab[0].type= AM_INDEX_SUBQUERY;
886
subselect_indexsubquery_engine(session,
894
else if (join_tab[0].type == AM_REF_OR_NULL &&
895
join_tab[0].ref.items[0]->name == in_left_expr_name &&
896
having->name == in_having_cond)
898
join_tab[0].type= AM_INDEX_SUBQUERY;
900
conds= remove_additional_cond(conds);
901
save_index_subquery_explain_info(join_tab, conds);
903
change_engine(new subselect_indexsubquery_engine(session,
913
Need to tell handlers that to play it safe, it should fetch all
914
columns of the primary key of the tables: this is because MySQL may
915
build row pointers for the rows, and for all columns of the primary key
916
the read set has not necessarily been set by the server code.
918
if (need_tmp || select_distinct || group_list || order)
920
for (uint32_t i = const_tables; i < tables; i++)
921
join_tab[i].table->prepare_for_position();
924
if (const_tables != tables)
927
Because filesort always does a full table scan or a quick range scan
928
we must add the removed reference to the select for the table.
929
We only need to do this when we have a simple_order or simple_group
930
as in other cases the join is done before the sort.
932
if ((order || group_list) &&
933
(join_tab[const_tables].type != AM_ALL) &&
934
(join_tab[const_tables].type != AM_REF_OR_NULL) &&
935
((order && simple_order) || (group_list && simple_group)))
937
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
942
if (!(select_options & SELECT_BIG_RESULT) &&
945
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
946
unit->select_limit_cnt, 0,
947
&join_tab[const_tables].table->
948
keys_in_use_for_group_by))) ||
950
tmp_table_param.quick_group)
952
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
957
Force using of tmp table if sorting by a SP or UDF function due to
958
their expensive and probably non-deterministic nature.
960
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
962
Item *item= *tmp_order->item;
963
if (item->is_expensive())
965
/* Force tmp table without sort */
966
need_tmp=1; simple_order=simple_group=0;
974
if (select_options & SELECT_DESCRIBE)
982
The loose index scan access method guarantees that all grouping or
983
duplicate row elimination (for distinct) is already performed
984
during data retrieval, and that all MIN/MAX functions are already
985
computed for each group. Thus all MIN/MAX functions should be
986
treated as regular functions, and there is no need to perform
987
grouping in the main execution loop.
988
Notice that currently loose index scan is applicable only for
989
single table queries, thus it is sufficient to test only the first
990
join_tab element of the plan for its access method.
992
if (join_tab->is_using_loose_index_scan())
993
tmp_table_param.precomputed_group_by= true;
995
/* Create a tmp table if distinct or if the sort is too complicated */
998
session->set_proc_info("Creating tmp table");
1000
init_items_ref_array();
1002
tmp_table_param.hidden_field_count= (all_fields.elements -
1003
fields_list.elements);
1004
order_st *tmp_group= ((!simple_group &&
1005
! (test_flags.test(TEST_NO_KEY_GROUP))) ? group_list :
1008
Pushing LIMIT to the temporary table creation is not applicable
1009
when there is ORDER BY or GROUP BY or there is no GROUP BY, but
1010
there are aggregate functions, because in all these cases we need
1013
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1015
!session->lex->current_select->with_sum_func) ?
1016
select_limit : HA_POS_ERROR;
1018
if (!(exec_tmp_table1=
1019
create_tmp_table(session, &tmp_table_param, all_fields,
1021
group_list ? 0 : select_distinct,
1022
group_list && simple_group,
1031
We don't have to store rows in temp table that doesn't match HAVING if:
1032
- we are sorting the table and writing complete group rows to the
1034
- We are using DISTINCT without resolving the distinct as a GROUP BY
1037
If having is not handled here, it will be checked before the row
1038
is sent to the client.
1040
if (tmp_having && (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1043
/* if group or order on first table, sort first */
1044
if (group_list && simple_group)
1046
session->set_proc_info("Sorting for group");
1047
if (create_sort_index(session, this, group_list,
1048
HA_POS_ERROR, HA_POS_ERROR, false) ||
1049
alloc_group_fields(this, group_list) ||
1050
make_sum_func_list(all_fields, fields_list, 1) ||
1051
setup_sum_funcs(session, sum_funcs))
1059
if (make_sum_func_list(all_fields, fields_list, 0) ||
1060
setup_sum_funcs(session, sum_funcs))
1065
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1067
session->set_proc_info("Sorting for order");
1068
if (create_sort_index(session, this, order,
1069
HA_POS_ERROR, HA_POS_ERROR, true))
1078
Optimize distinct when used on some of the tables
1079
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1080
In this case we can stop scanning t2 when we have found one t1.a
1083
if (exec_tmp_table1->distinct)
1085
table_map used_tables= session->used_tables;
1086
JoinTable *last_join_tab= join_tab+tables-1;
1089
if (used_tables & last_join_tab->table->map)
1091
last_join_tab->not_used_in_distinct=1;
1092
} while (last_join_tab-- != join_tab);
1093
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1094
if (order && skip_sort_order)
1096
/* Should always succeed */
1097
if (test_if_skip_sort_order(&join_tab[const_tables],
1098
order, unit->select_limit_cnt, 0,
1099
&join_tab[const_tables].table->
1100
keys_in_use_for_order_by))
1106
If this join belongs to an uncacheable subquery save
1109
if (select_lex->uncacheable && !is_top_level_join() &&
1110
init_save_join_tab())
1119
Restore values in temporary join.
1121
void JOIN::restore_tmp()
1123
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1128
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1129
select_lex->offset_limit->val_uint() :
1134
if (exec_tmp_table1)
1136
exec_tmp_table1->cursor->extra(HA_EXTRA_RESET_STATE);
1137
exec_tmp_table1->cursor->ha_delete_all_rows();
1138
exec_tmp_table1->free_io_cache();
1139
exec_tmp_table1->filesort_free_buffers();
1141
if (exec_tmp_table2)
1143
exec_tmp_table2->cursor->extra(HA_EXTRA_RESET_STATE);
1144
exec_tmp_table2->cursor->ha_delete_all_rows();
1145
exec_tmp_table2->free_io_cache();
1146
exec_tmp_table2->filesort_free_buffers();
1149
set_items_ref_array(items0);
1152
memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);
1157
/* Reset of sum functions */
1160
Item_sum *func, **func_ptr= sum_funcs;
1161
while ((func= *(func_ptr++)))
1169
@brief Save the original join layout
1171
@details Saves the original join layout so it can be reused in
1172
re-execution and for EXPLAIN.
1174
@return Operation status
1176
@retval 1 error occurred.
1178
bool JOIN::init_save_join_tab()
1180
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
1182
error= 0; // Ensure that tmp_join.error= 0
1187
bool JOIN::save_join_tab()
1189
if (!join_tab_save && select_lex->master_unit()->uncacheable)
1191
if (!(join_tab_save= (JoinTable*)session->memdup((unsigned char*) join_tab,
1192
sizeof(JoinTable) * tables)))
1202
Note, that create_sort_index calls test_if_skip_sort_order and may
1203
finally replace sorting with index scan if there is a LIMIT clause in
1204
the query. It's never shown in EXPLAIN!
1207
When can we have here session->net.report_error not zero?
1211
List<Item> *columns_list= &fields_list;
1214
session->set_proc_info("executing");
1217
if (!tables_list && (tables || !select_lex->with_sum_func))
1219
/* Only test of functions */
1220
if (select_options & SELECT_DESCRIBE)
1222
optimizer::ExplainPlan planner(this,
1226
(zero_result_cause ? zero_result_cause : "No tables used"));
1227
planner.printPlan();
1231
result->send_fields(*columns_list);
1233
We have to test for 'conds' here as the WHERE may not be constant
1234
even if we don't have any tables for prepared statements or if
1235
conds uses something like 'rand()'.
1237
if (cond_value != Item::COND_FALSE &&
1238
(!conds || conds->val_int()) &&
1239
(!having || having->val_int()))
1241
if (do_send_rows && result->send_data(fields_list))
1245
error= (int) result->send_eof();
1246
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
1251
error= (int) result->send_eof();
1255
/* Single select (without union) always returns 0 or 1 row */
1256
session->limit_found_rows= send_records;
1257
session->examined_row_count= 0;
1261
Don't reset the found rows count if there're no tables as
1262
FOUND_ROWS() may be called. Never reset the examined row count here.
1263
It must be accumulated from all join iterations of all join parts.
1266
session->limit_found_rows= 0;
1268
if (zero_result_cause)
1270
(void) return_zero_rows(this, result, select_lex->leaf_tables,
1272
send_row_on_empty_set(),
1279
if (select_options & SELECT_DESCRIBE)
1282
Check if we managed to optimize ORDER BY away and don't use temporary
1283
table to resolve order_st BY: in that case, we only may need to do
1284
filesort for GROUP BY.
1286
if (!order && !no_order && (!skip_sort_order || !need_tmp))
1288
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
1290
simple_order= simple_group;
1293
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
1295
if (const_tables == tables
1296
|| ((simple_order || skip_sort_order)
1297
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
1301
optimizer::ExplainPlan planner(this,
1303
order != 0 && ! skip_sort_order,
1305
! tables ? "No tables used" : NULL);
1306
planner.printPlan();
1310
JOIN *curr_join= this;
1311
List<Item> *curr_all_fields= &all_fields;
1312
List<Item> *curr_fields_list= &fields_list;
1313
Table *curr_tmp_table= 0;
1315
Initialize examined rows here because the values from all join parts
1316
must be accumulated in examined_row_count. Hence every join
1317
iteration must count from zero.
1319
curr_join->examined_rows= 0;
1321
/* Create a tmp table if distinct or if the sort is too complicated */
1327
We are in a non cacheable sub query. Get the saved join structure
1329
(curr_join may have been modified during last exection and we need
1332
curr_join= tmp_join;
1334
curr_tmp_table= exec_tmp_table1;
1336
/* Copy data to the temporary table */
1337
session->set_proc_info("Copying to tmp table");
1338
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
1339
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1340
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1345
curr_tmp_table->cursor->info(HA_STATUS_VARIABLE);
1347
if (curr_join->having)
1348
curr_join->having= curr_join->tmp_having= 0; // Allready done
1350
/* Change sum_fields reference to calculated fields in tmp_table */
1351
curr_join->all_fields= *curr_all_fields;
1354
items1= items0 + all_fields.elements;
1355
if (sort_and_group || curr_tmp_table->group)
1357
if (change_to_use_tmp_fields(session, items1,
1358
tmp_fields_list1, tmp_all_fields1,
1359
fields_list.elements, all_fields))
1364
if (change_refs_to_tmp_fields(session, items1,
1365
tmp_fields_list1, tmp_all_fields1,
1366
fields_list.elements, all_fields))
1369
curr_join->tmp_all_fields1= tmp_all_fields1;
1370
curr_join->tmp_fields_list1= tmp_fields_list1;
1371
curr_join->items1= items1;
1373
curr_all_fields= &tmp_all_fields1;
1374
curr_fields_list= &tmp_fields_list1;
1375
curr_join->set_items_ref_array(items1);
1377
if (sort_and_group || curr_tmp_table->group)
1379
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
1380
+ curr_join->tmp_table_param.func_count;
1381
curr_join->tmp_table_param.sum_func_count= 0;
1382
curr_join->tmp_table_param.func_count= 0;
1386
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
1387
curr_join->tmp_table_param.func_count= 0;
1390
if (curr_tmp_table->group)
1391
{ // Already grouped
1392
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
1393
curr_join->order= curr_join->group_list; /* order by group */
1394
curr_join->group_list= 0;
1398
If we have different sort & group then we must sort the data by group
1399
and copy it to another tmp table
1400
This code is also used if we are using distinct something
1401
we haven't been able to store in the temporary table yet
1402
like SEC_TO_TIME(SUM(...)).
1405
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
1406
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
1407
{ /* Must copy to another table */
1408
/* Free first data from old join */
1409
curr_join->join_free();
1410
if (make_simple_join(curr_join, curr_tmp_table))
1412
calc_group_buffer(curr_join, group_list);
1413
count_field_types(select_lex, &curr_join->tmp_table_param,
1414
curr_join->tmp_all_fields1,
1415
curr_join->select_distinct && !curr_join->group_list);
1416
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
1417
- curr_join->tmp_fields_list1.elements;
1419
if (exec_tmp_table2)
1420
curr_tmp_table= exec_tmp_table2;
1423
/* group data to new table */
1426
If the access method is loose index scan then all MIN/MAX
1427
functions are precomputed, and should be treated as regular
1428
functions. See extended comment in JOIN::exec.
1430
if (curr_join->join_tab->is_using_loose_index_scan())
1431
curr_join->tmp_table_param.precomputed_group_by= true;
1433
if (!(curr_tmp_table=
1434
exec_tmp_table2= create_tmp_table(session,
1435
&curr_join->tmp_table_param,
1438
curr_join->select_distinct &&
1439
!curr_join->group_list,
1440
1, curr_join->select_options,
1444
curr_join->exec_tmp_table2= exec_tmp_table2;
1446
if (curr_join->group_list)
1448
session->set_proc_info("Creating sort index");
1449
if (curr_join->join_tab == join_tab && save_join_tab())
1453
if (create_sort_index(session, curr_join, curr_join->group_list,
1454
HA_POS_ERROR, HA_POS_ERROR, false) ||
1455
make_group_fields(this, curr_join))
1459
sortorder= curr_join->sortorder;
1462
session->set_proc_info("Copying to group table");
1464
if (curr_join != this)
1468
curr_join->sum_funcs= sum_funcs2;
1469
curr_join->sum_funcs_end= sum_funcs_end2;
1473
curr_join->alloc_func_list();
1474
sum_funcs2= curr_join->sum_funcs;
1475
sum_funcs_end2= curr_join->sum_funcs_end;
1478
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
1480
curr_join->group_list= 0;
1482
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
1483
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1485
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
1486
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1491
end_read_record(&curr_join->join_tab->read_record);
1492
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1493
curr_join->join_tab[0].table= 0; // Table is freed
1495
// No sum funcs anymore
1498
items2= items1 + all_fields.elements;
1499
if (change_to_use_tmp_fields(session, items2,
1500
tmp_fields_list2, tmp_all_fields2,
1501
fields_list.elements, tmp_all_fields1))
1503
curr_join->tmp_fields_list2= tmp_fields_list2;
1504
curr_join->tmp_all_fields2= tmp_all_fields2;
1506
curr_fields_list= &curr_join->tmp_fields_list2;
1507
curr_all_fields= &curr_join->tmp_all_fields2;
1508
curr_join->set_items_ref_array(items2);
1509
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
1510
curr_join->tmp_table_param.sum_func_count= 0;
1512
if (curr_tmp_table->distinct)
1513
curr_join->select_distinct=0; /* Each row is unique */
1515
curr_join->join_free(); /* Free quick selects */
1516
if (curr_join->select_distinct && ! curr_join->group_list)
1518
session->set_proc_info("Removing duplicates");
1519
if (curr_join->tmp_having)
1520
curr_join->tmp_having->update_used_tables();
1522
if (remove_duplicates(curr_join, curr_tmp_table,
1523
*curr_fields_list, curr_join->tmp_having))
1526
curr_join->tmp_having=0;
1527
curr_join->select_distinct=0;
1529
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
1530
if (make_simple_join(curr_join, curr_tmp_table))
1532
calc_group_buffer(curr_join, curr_join->group_list);
1533
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
1537
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
1539
if (make_group_fields(this, curr_join))
1545
init_items_ref_array();
1546
items3= ref_pointer_array + (all_fields.elements*4);
1547
setup_copy_fields(session, &curr_join->tmp_table_param,
1548
items3, tmp_fields_list3, tmp_all_fields3,
1549
curr_fields_list->elements, *curr_all_fields);
1550
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
1551
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
1552
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
1553
curr_join->tmp_all_fields3= tmp_all_fields3;
1554
curr_join->tmp_fields_list3= tmp_fields_list3;
1558
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
1559
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
1560
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
1562
curr_fields_list= &tmp_fields_list3;
1563
curr_all_fields= &tmp_all_fields3;
1564
curr_join->set_items_ref_array(items3);
1566
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1568
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
1569
session->is_fatal_error)
1572
if (curr_join->group_list || curr_join->order)
1574
session->set_proc_info("Sorting result");
1575
/* If we have already done the group, add HAVING to sorted table */
1576
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
1578
// Some tables may have been const
1579
curr_join->tmp_having->update_used_tables();
1580
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];
1581
table_map used_tables= (curr_join->const_table_map |
1582
curr_table->table->map);
1584
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
1585
if (sort_table_cond)
1587
if (!curr_table->select)
1588
if (!(curr_table->select= new optimizer::SqlSelect))
1590
if (!curr_table->select->cond)
1591
curr_table->select->cond= sort_table_cond;
1592
else // This should never happen
1594
if (!(curr_table->select->cond=
1595
new Item_cond_and(curr_table->select->cond,
1599
Item_cond_and do not need fix_fields for execution, its parameters
1600
are fixed or do not need fix_fields, too
1602
curr_table->select->cond->quick_fix_field();
1604
curr_table->select_cond= curr_table->select->cond;
1605
curr_table->select_cond->top_level_item();
1606
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
1613
curr_join->select_limit= HA_POS_ERROR;
1617
We can abort sorting after session->select_limit rows if we there is no
1618
WHERE clause for any tables after the sorted one.
1620
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
1621
JoinTable *end_table= &curr_join->join_tab[curr_join->tables];
1622
for (; curr_table < end_table ; curr_table++)
1625
table->keyuse is set in the case there was an original WHERE clause
1626
on the table that was optimized away.
1628
if (curr_table->select_cond ||
1629
(curr_table->keyuse && !curr_table->first_inner))
1631
/* We have to sort all rows */
1632
curr_join->select_limit= HA_POS_ERROR;
1637
if (curr_join->join_tab == join_tab && save_join_tab())
1640
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
1641
chose FILESORT to be faster than INDEX SCAN or there is no
1642
suitable index present.
1643
Note, that create_sort_index calls test_if_skip_sort_order and may
1644
finally replace sorting with index scan if there is a LIMIT clause in
1645
the query. XXX: it's never shown in EXPLAIN!
1646
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
1648
if (create_sort_index(session, curr_join,
1649
curr_join->group_list ?
1650
curr_join->group_list : curr_join->order,
1651
curr_join->select_limit,
1652
(select_options & OPTION_FOUND_ROWS ?
1653
HA_POS_ERROR : unit->select_limit_cnt),
1654
curr_join->group_list ? true : false))
1657
sortorder= curr_join->sortorder;
1658
if (curr_join->const_tables != curr_join->tables &&
1659
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
1662
If no IO cache exists for the first table then we are using an
1663
INDEX SCAN and no filesort. Thus we should not remove the sorted
1664
attribute on the INDEX SCAN.
1670
/* XXX: When can we have here session->is_error() not zero? */
1671
if (session->is_error())
1673
error= session->is_error();
1676
curr_join->having= curr_join->tmp_having;
1677
curr_join->fields= curr_fields_list;
1679
session->set_proc_info("Sending data");
1680
result->send_fields(*curr_fields_list);
1681
error= do_select(curr_join, curr_fields_list, NULL);
1682
session->limit_found_rows= curr_join->send_records;
1684
/* Accumulate the counts from all join iterations of all join parts. */
1685
session->examined_row_count+= curr_join->examined_rows;
1688
With EXPLAIN EXTENDED we have to restore original ref_array
1689
for a derived table which is always materialized.
1690
Otherwise we would not be able to print the query correctly.
1692
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
1693
set_items_ref_array(items0);
1702
Return error that hold JOIN.
1706
select_lex->join= 0;
1710
if (join_tab != tmp_join->join_tab)
1712
JoinTable *tab, *end;
1713
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
1716
tmp_join->tmp_join= 0;
1717
tmp_table_param.copy_field=0;
1718
return(tmp_join->destroy());
1723
if (exec_tmp_table1)
1724
exec_tmp_table1->free_tmp_table(session);
1725
if (exec_tmp_table2)
1726
exec_tmp_table2->free_tmp_table(session);
1728
delete_dynamic(&keyuse);
1733
Setup for execution all subqueries of a query, for which the optimizer
1734
chose hash semi-join.
1736
@details Iterate over all subqueries of the query, and if they are under an
1737
IN predicate, and the optimizer chose to compute it via hash semi-join:
1738
- try to initialize all data structures needed for the materialized execution
1739
of the IN predicate,
1740
- if this fails, then perform the IN=>EXISTS transformation which was
1741
previously blocked during JOIN::prepare.
1743
This method is part of the "code generation" query processing phase.
1745
This phase must be called after substitute_for_best_equal_field() because
1746
that function may replace items with other items from a multiple equality,
1747
and we need to reference the correct items in the index access method of the
1750
@return Operation status
1751
@retval false success.
1752
@retval true error occurred.
1754
bool JOIN::setup_subquery_materialization()
1756
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1757
un= un->next_unit())
1759
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
1761
Item_subselect *subquery_predicate= sl->master_unit()->item;
1762
if (subquery_predicate &&
1763
subquery_predicate->substype() == Item_subselect::IN_SUBS)
1765
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
1766
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
1767
in_subs->setup_engine())
1776
Partially cleanup JOIN after it has executed: close index or rnd read
1777
(table cursors), free quick selects.
1779
This function is called in the end of execution of a JOIN, before the used
1780
tables are unlocked and closed.
1782
For a join that is resolved using a temporary table, the first sweep is
1783
performed against actual tables and an intermediate result is inserted
1784
into the temprorary table.
1785
The last sweep is performed against the temporary table. Therefore,
1786
the base tables and associated buffers used to fill the temporary table
1787
are no longer needed, and this function is called to free them.
1789
For a join that is performed without a temporary table, this function
1790
is called after all rows are sent, but before EOF packet is sent.
1792
For a simple SELECT with no subqueries this function performs a full
1793
cleanup of the JOIN and calls mysql_unlock_read_tables to free used base
1796
If a JOIN is executed for a subquery or if it has a subquery, we can't
1797
do the full cleanup and need to do a partial cleanup only.
1798
- If a JOIN is not the top level join, we must not unlock the tables
1799
because the outer select may not have been evaluated yet, and we
1800
can't unlock only selected tables of a query.
1801
- Additionally, if this JOIN corresponds to a correlated subquery, we
1802
should not free quick selects and join buffers because they will be
1803
needed for the next execution of the correlated subquery.
1804
- However, if this is a JOIN for a [sub]select, which is not
1805
a correlated subquery itself, but has subqueries, we can free it
1806
fully and also free JOINs of all its subqueries. The exception
1807
is a subquery in SELECT list, e.g: @n
1808
SELECT a, (select cmax(b) from t1) group by c @n
1809
This subquery will not be evaluated at first sweep and its value will
1810
not be inserted into the temporary table. Instead, it's evaluated
1811
when selecting from the temporary table. Therefore, it can't be freed
1812
here even though it's not correlated.
1815
Unlock tables even if the join isn't top level select in the tree
1817
void JOIN::join_free()
1819
Select_Lex_Unit *tmp_unit;
1822
Optimization: if not EXPLAIN and we are done with the JOIN,
1825
bool full= (!select_lex->uncacheable && !session->lex->describe);
1826
bool can_unlock= full;
1830
for (tmp_unit= select_lex->first_inner_unit();
1832
tmp_unit= tmp_unit->next_unit())
1833
for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
1835
Item_subselect *subselect= sl->master_unit()->item;
1836
bool full_local= full && (!subselect || subselect->is_evaluated());
1838
If this join is evaluated, we can fully clean it up and clean up all
1839
its underlying joins even if they are correlated -- they will not be
1840
used any more anyway.
1841
If this join is not yet evaluated, we still must clean it up to
1842
close its table cursors -- it may never get evaluated, as in case of
1843
... HAVING false OR a IN (SELECT ...))
1844
but all table cursors must be closed before the unlock.
1846
sl->cleanup_all_joins(full_local);
1847
/* Can't unlock if at least one JOIN is still needed */
1848
can_unlock= can_unlock && full_local;
1852
We are not using tables anymore
1853
Unlock all tables. We may be in an INSERT .... SELECT statement.
1855
if (can_unlock && lock && session->lock &&
1856
!(select_options & SELECT_NO_UNLOCK) &&
1857
!select_lex->subquery_in_having &&
1858
(select_lex == (session->lex->unit.fake_select_lex ?
1859
session->lex->unit.fake_select_lex : &session->lex->select_lex)))
1862
TODO: unlock tables even if the join isn't top level select in the
1865
mysql_unlock_read_tables(session, lock); // Don't free join->lock
1874
Free resources of given join.
1876
@param fill true if we should free all resources, call with full==1
1877
should be last, before it this function can be called with
1881
With subquery this function definitely will be called several times,
1882
but even for simple query it can be called several times.
1884
void JOIN::cleanup(bool full)
1888
JoinTable *tab,*end;
1890
Only a sorted table may be cached. This sorted table is always the
1891
first non const table in join->table
1893
if (tables > const_tables) // Test for not-const tables
1895
table[const_tables]->free_io_cache();
1896
table[const_tables]->filesort_free_buffers(full);
1901
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1907
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1910
tab->table->cursor->ha_index_or_rnd_end();
1915
We are not using tables anymore
1916
Unlock all tables. We may be in an INSERT .... SELECT statement.
1921
tmp_table_param.copy_field= 0;
1922
group_fields.delete_elements();
1924
We can't call delete_elements() on copy_funcs as this will cause
1925
problems in free_elements() as some of the elements are then deleted.
1927
tmp_table_param.copy_funcs.empty();
1929
If we have tmp_join and 'this' JOIN is not tmp_join and
1930
tmp_table_param.copy_field's of them are equal then we have to remove
1931
pointer to tmp_table_param.copy_field from tmp_join, because it qill
1932
be removed in tmp_table_param.cleanup().
1936
tmp_join->tmp_table_param.copy_field ==
1937
tmp_table_param.copy_field)
1939
tmp_join->tmp_table_param.copy_field=
1940
tmp_join->tmp_table_param.save_copy_field= 0;
1942
tmp_table_param.cleanup();
1948
used only in JOIN::clear
1950
static void clear_tables(JOIN *join)
1953
must clear only the non-const tables, as const tables
1954
are not re-calculated.
1956
for (uint32_t i= join->const_tables; i < join->tables; i++)
1957
join->table[i]->mark_as_null_row(); // All fields are NULL
1961
Make an array of pointers to sum_functions to speed up
1962
sum_func calculation.
1969
bool JOIN::alloc_func_list()
1971
uint32_t func_count, group_parts;
1973
func_count= tmp_table_param.sum_func_count;
1975
If we are using rollup, we need a copy of the summary functions for
1978
if (rollup.state != ROLLUP::STATE_NONE)
1979
func_count*= (send_group_parts+1);
1981
group_parts= send_group_parts;
1983
If distinct, reserve memory for possible
1984
disctinct->group_by optimization
1986
if (select_distinct)
1988
group_parts+= fields_list.elements;
1990
If the order_st clause is specified then it's possible that
1991
it also will be optimized, so reserve space for it too
1996
for (ord= order; ord; ord= ord->next)
2001
/* This must use calloc() as rollup_make_fields depends on this */
2002
sum_funcs= (Item_sum**) session->calloc(sizeof(Item_sum**) * (func_count+1) +
2003
sizeof(Item_sum***) * (group_parts+1));
2004
sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
2005
return(sum_funcs == 0);
2009
Initialize 'sum_funcs' array with all Item_sum objects.
2011
@param field_list All items
2012
@param send_fields Items in select list
2013
@param before_group_by Set to 1 if this is called before GROUP BY handling
2014
@param recompute Set to true if sum_funcs must be recomputed
2021
bool JOIN::make_sum_func_list(List<Item> &field_list,
2022
List<Item> &send_fields,
2023
bool before_group_by,
2026
List_iterator_fast<Item> it(field_list);
2030
if (*sum_funcs && !recompute)
2031
return(false); /* We have already initialized sum_funcs. */
2036
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2037
(!((Item_sum*) item)->depended_from() ||
2038
((Item_sum *)item)->depended_from() == select_lex))
2039
*func++= (Item_sum*) item;
2041
if (before_group_by && rollup.state == ROLLUP::STATE_INITED)
2043
rollup.state= ROLLUP::STATE_READY;
2044
if (rollup_make_fields(field_list, send_fields, &func))
2045
return(true); // Should never happen
2047
else if (rollup.state == ROLLUP::STATE_NONE)
2049
for (uint32_t i=0 ; i <= send_group_parts ;i++)
2050
sum_funcs_end[i]= func;
2052
else if (rollup.state == ROLLUP::STATE_READY)
2053
return(false); // Don't put end marker
2054
*func=0; // End marker
2058
/** Allocate memory needed for other rollup functions. */
2059
bool JOIN::rollup_init()
2064
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2065
rollup.state= ROLLUP::STATE_INITED;
2068
Create pointers to the different sum function groups
2069
These are updated by rollup_make_fields()
2071
tmp_table_param.group_parts= send_group_parts;
2073
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
2075
sizeof(List<Item>) +
2076
ref_pointer_array_size)
2077
* send_group_parts )))
2080
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
2081
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
2082
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
2085
Prepare space for field list for the different levels
2086
These will be filled up in rollup_make_fields()
2088
for (i= 0 ; i < send_group_parts ; i++)
2090
rollup.null_items[i]= new (session->mem_root) Item_null_result();
2091
List<Item> *rollup_fields= &rollup.fields[i];
2092
rollup_fields->empty();
2093
rollup.ref_pointer_arrays[i]= ref_array;
2094
ref_array+= all_fields.elements;
2096
for (i= 0 ; i < send_group_parts; i++)
2098
for (j=0 ; j < fields_list.elements ; j++)
2099
rollup.fields[i].push_back(rollup.null_items[i]);
2101
List_iterator<Item> it(all_fields);
2103
while ((item= it++))
2105
order_st *group_tmp;
2106
bool found_in_group= 0;
2108
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2110
if (*group_tmp->item == item)
2112
item->maybe_null= 1;
2114
if (item->const_item())
2117
For ROLLUP queries each constant item referenced in GROUP BY list
2118
is wrapped up into an Item_func object yielding the same value
2119
as the constant item. The objects of the wrapper class are never
2120
considered as constant items and besides they inherit all
2121
properties of the Item_result_field class.
2122
This wrapping allows us to ensure writing constant items
2123
into temporary tables whenever the result of the ROLLUP
2124
operation has to be written into a temporary table, e.g. when
2125
ROLLUP is used together with DISTINCT in the SELECT list.
2126
Usually when creating temporary tables for a intermidiate
2127
result we do not include fields for constant expressions.
2129
Item* new_item= new Item_func_rollup_const(item);
2132
new_item->fix_fields(session, (Item **) 0);
2133
session->change_item_tree(it.ref(), new_item);
2134
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
2136
if (*tmp->item == item)
2137
session->change_item_tree(tmp->item, new_item);
2142
if (item->type() == Item::FUNC_ITEM && !found_in_group)
2144
bool changed= false;
2145
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
2148
We have to prevent creation of a field in a temporary table for
2149
an expression that contains GROUP BY attributes.
2150
Marking the expression item as 'with_sum_func' will ensure this.
2153
item->with_sum_func= 1;
2160
Fill up rollup structures with pointers to fields to use.
2162
Creates copies of item_sum items for each sum level.
2164
@param fields_arg List of all fields (hidden and real ones)
2165
@param sel_fields Pointer to selected fields
2166
@param func Store here a pointer to all fields
2170
In this case func is pointing to next not used element.
2174
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2176
List_iterator_fast<Item> it(fields_arg);
2177
Item *first_field= sel_fields.head();
2181
Create field lists for the different levels
2183
The idea here is to have a separate field list for each rollup level to
2184
avoid all runtime checks of which columns should be NULL.
2186
The list is stored in reverse order to get sum function in such an order
2187
in func that it makes it easy to reset them with init_sum_functions()
2189
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2191
rollup.fields[0] will contain list where a,b,c is NULL
2192
rollup.fields[1] will contain list where b,c is NULL
2194
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
2196
sum_funcs_end[0] points to all sum functions
2197
sum_funcs_end[1] points to all sum functions, except grand totals
2201
for (level=0 ; level < send_group_parts ; level++)
2204
uint32_t pos= send_group_parts - level -1;
2205
bool real_fields= 0;
2207
List_iterator<Item> new_it(rollup.fields[pos]);
2208
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
2209
order_st *start_group;
2211
/* Point to first hidden field */
2212
Item **ref_array= ref_array_start + fields_arg.elements-1;
2214
/* Remember where the sum functions ends for the previous level */
2215
sum_funcs_end[pos+1]= *func;
2217
/* Find the start of the group for this level */
2218
for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
2222
while ((item= it++))
2224
if (item == first_field)
2226
real_fields= 1; // End of hidden fields
2227
ref_array= ref_array_start;
2230
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2231
(!((Item_sum*) item)->depended_from() ||
2232
((Item_sum *)item)->depended_from() == select_lex))
2236
This is a top level summary function that must be replaced with
2237
a sum function that is reset for this level.
2239
NOTE: This code creates an object which is not that nice in a
2240
sub select. Fortunately it's not common to have rollup in
2243
item= item->copy_or_same(session);
2244
((Item_sum*) item)->make_unique();
2245
*(*func)= (Item_sum*) item;
2250
/* Check if this is something that is part of this group by */
2251
order_st *group_tmp;
2252
for (group_tmp= start_group, i= pos ;
2253
group_tmp ; group_tmp= group_tmp->next, i++)
2255
if (*group_tmp->item == item)
2258
This is an element that is used by the GROUP BY and should be
2259
set to NULL in this level
2261
Item_null_result *null_item= new (session->mem_root) Item_null_result();
2264
item->maybe_null= 1; // Value will be null sometimes
2265
null_item->result_field= item->get_tmp_table_field();
2274
(void) new_it++; // Point to next item
2275
new_it.replace(item); // Replace previous
2282
sum_funcs_end[0]= *func; // Point to last function
2287
Send all rollup levels higher than the current one to the client.
2291
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2294
@param idx Level we are on:
2295
- 0 = Total sum level
2296
- 1 = First group changed (a)
2297
- 2 = Second group changed (a,b)
2302
1 If send_data_failed()
2304
int JOIN::rollup_send_data(uint32_t idx)
2307
for (i= send_group_parts ; i-- > idx ; )
2309
/* Get reference pointers to sum functions in place */
2310
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2311
ref_pointer_array_size);
2312
if ((!having || having->val_int()))
2314
if (send_records < unit->select_limit_cnt && do_send_rows &&
2315
result->send_data(rollup.fields[i]))
2320
/* Restore ref_pointer_array */
2321
set_items_ref_array(current_ref_pointer_array);
2326
Write all rollup levels higher than the current one to a temp table.
2330
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
2333
@param idx Level we are on:
2334
- 0 = Total sum level
2335
- 1 = First group changed (a)
2336
- 2 = Second group changed (a,b)
2337
@param table reference to temp table
2342
1 if write_data_failed()
2344
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
2347
for (i= send_group_parts ; i-- > idx ; )
2349
/* Get reference pointers to sum functions in place */
2350
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2351
ref_pointer_array_size);
2352
if ((!having || having->val_int()))
2356
List_iterator_fast<Item> it(rollup.fields[i]);
2357
while ((item= it++))
2359
if (item->type() == Item::NULL_ITEM && item->is_result_field())
2360
item->save_in_result_field(1);
2362
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2363
if ((write_error= table_arg->cursor->ha_write_row(table_arg->record[0])))
2365
if (create_myisam_from_heap(session, table_arg,
2366
tmp_table_param.start_recinfo,
2367
&tmp_table_param.recinfo,
2373
/* Restore ref_pointer_array */
2374
set_items_ref_array(current_ref_pointer_array);
2379
clear results if there are not rows found for group
2380
(end_send_group/end_write_group)
2385
copy_fields(&tmp_table_param);
2389
Item_sum *func, **func_ptr= sum_funcs;
2390
while ((func= *(func_ptr++)))
2396
change select_result object of JOIN.
2398
@param res new select_result object
2405
bool JOIN::change_result(select_result *res)
2408
if (result->prepare(fields_list, select_lex->master_unit()))
2416
Cache constant expressions in WHERE, HAVING, ON conditions.
2419
void JOIN::cache_const_exprs()
2421
bool cache_flag= false;
2422
bool *analyzer_arg= &cache_flag;
2424
/* No need in cache if all tables are constant. */
2425
if (const_tables == tables)
2429
conds->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2430
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2433
having->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2434
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2436
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
2438
if (*tab->on_expr_ref)
2441
(*tab->on_expr_ref)->compile(&Item::cache_const_expr_analyzer,
2442
(unsigned char **)&analyzer_arg,
2443
&Item::cache_const_expr_transformer,
2444
(unsigned char *)&cache_flag);
2452
Process one record of the nested loop join.
2456
This function will evaluate parts of WHERE/ON clauses that are
2457
applicable to the partial record on hand and in case of success
2458
submit this record to the next level of the nested loop.
2460
enum_nested_loop_state evaluate_join_record(JOIN *join, JoinTable *join_tab, int error)
2462
bool not_used_in_distinct= join_tab->not_used_in_distinct;
2463
ha_rows found_records= join->found_records;
2464
COND *select_cond= join_tab->select_cond;
2466
if (error > 0 || (join->session->is_error())) // Fatal error
2467
return NESTED_LOOP_ERROR;
2469
return NESTED_LOOP_NO_MORE_ROWS;
2470
if (join->session->killed) // Aborted by user
2472
join->session->send_kill_message();
2473
return NESTED_LOOP_KILLED;
2475
if (!select_cond || select_cond->val_int())
2478
There is no select condition or the attached pushed down
2479
condition is true => a match is found.
2482
while (join_tab->first_unmatched && found)
2485
The while condition is always false if join_tab is not
2486
the last inner join table of an outer join operation.
2488
JoinTable *first_unmatched= join_tab->first_unmatched;
2490
Mark that a match for current outer table is found.
2491
This activates push down conditional predicates attached
2492
to the all inner tables of the outer join.
2494
first_unmatched->found= 1;
2495
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2497
if (tab->table->reginfo.not_exists_optimize)
2498
return NESTED_LOOP_NO_MORE_ROWS;
2499
/* Check all predicates that has just been activated. */
2501
Actually all predicates non-guarded by first_unmatched->found
2502
will be re-evaluated again. It could be fixed, but, probably,
2503
it's not worth doing now.
2505
if (tab->select_cond && !tab->select_cond->val_int())
2507
/* The condition attached to table tab is false */
2508
if (tab == join_tab)
2513
Set a return point if rejected predicate is attached
2514
not to the last table of the current nest level.
2516
join->return_tab= tab;
2517
return NESTED_LOOP_OK;
2522
Check whether join_tab is not the last inner table
2523
for another embedding outer join.
2525
if ((first_unmatched= first_unmatched->first_upper) &&
2526
first_unmatched->last_inner != join_tab)
2528
join_tab->first_unmatched= first_unmatched;
2531
JoinTable *return_tab= join->return_tab;
2532
join_tab->found_match= true;
2535
It was not just a return to lower loop level when one
2536
of the newly activated predicates is evaluated as false
2537
(See above join->return_tab= tab).
2539
join->examined_rows++;
2540
join->session->row_count++;
2544
enum enum_nested_loop_state rc;
2545
/* A match from join_tab is found for the current partial join. */
2546
rc= (*join_tab->next_select)(join, join_tab+1, 0);
2547
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2549
if (return_tab < join->return_tab)
2550
join->return_tab= return_tab;
2552
if (join->return_tab < join_tab)
2553
return NESTED_LOOP_OK;
2555
Test if this was a SELECT DISTINCT query on a table that
2556
was not in the field list; In this case we can abort if
2557
we found a row, as no new rows can be added to the result.
2559
if (not_used_in_distinct && found_records != join->found_records)
2560
return NESTED_LOOP_NO_MORE_ROWS;
2563
join_tab->read_record.cursor->unlock_row();
2568
The condition pushed down to the table join_tab rejects all rows
2569
with the beginning coinciding with the current partial join.
2571
join->examined_rows++;
2572
join->session->row_count++;
2573
join_tab->read_record.cursor->unlock_row();
2575
return NESTED_LOOP_OK;
2580
Construct a NULL complimented partial join record and feed it to the next
2581
level of the nested loop. This function is used in case we have
2582
an OUTER join and no matching record was found.
2584
enum_nested_loop_state evaluate_null_complemented_join_record(JOIN *join, JoinTable *join_tab)
2587
The table join_tab is the first inner table of a outer join operation
2588
and no matches has been found for the current outer row.
2590
JoinTable *last_inner_tab= join_tab->last_inner;
2591
/* Cache variables for faster loop */
2593
for ( ; join_tab <= last_inner_tab ; join_tab++)
2595
/* Change the the values of guard predicate variables. */
2597
join_tab->not_null_compl= 0;
2598
/* The outer row is complemented by nulls for each inner tables */
2599
join_tab->table->restoreRecordAsDefault(); // Make empty record
2600
join_tab->table->mark_as_null_row(); // For group by without error
2601
select_cond= join_tab->select_cond;
2602
/* Check all attached conditions for inner table rows. */
2603
if (select_cond && !select_cond->val_int())
2604
return NESTED_LOOP_OK;
2608
The row complemented by nulls might be the first row
2609
of embedding outer joins.
2610
If so, perform the same actions as in the code
2611
for the first regular outer join row above.
2615
JoinTable *first_unmatched= join_tab->first_unmatched;
2616
if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
2618
join_tab->first_unmatched= first_unmatched;
2619
if (! first_unmatched)
2621
first_unmatched->found= 1;
2622
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2624
if (tab->select_cond && !tab->select_cond->val_int())
2626
join->return_tab= tab;
2627
return NESTED_LOOP_OK;
2632
The row complemented by nulls satisfies all conditions
2633
attached to inner tables.
2634
Send the row complemented by nulls to be joined with the
2637
return (*join_tab->next_select)(join, join_tab+1, 0);
2640
enum_nested_loop_state flush_cached_records(JOIN *join, JoinTable *join_tab, bool skip_last)
2642
enum_nested_loop_state rc= NESTED_LOOP_OK;
2646
join_tab->table->null_row= 0;
2647
if (!join_tab->cache.records)
2648
return NESTED_LOOP_OK; /* Nothing to do */
2650
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
2651
if (join_tab->use_quick == 2)
2653
if (join_tab->select->quick)
2654
{ /* Used quick select last. reset it */
2655
delete join_tab->select->quick;
2656
join_tab->select->quick=0;
2659
/* read through all records */
2660
if ((error=join_init_read_record(join_tab)))
2662
reset_cache_write(&join_tab->cache);
2663
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2666
for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)
2668
tmp->status=tmp->table->status;
2669
tmp->table->status=0;
2672
info= &join_tab->read_record;
2675
if (join->session->killed)
2677
join->session->send_kill_message();
2678
return NESTED_LOOP_KILLED;
2680
optimizer::SqlSelect *select= join_tab->select;
2681
if (rc == NESTED_LOOP_OK &&
2682
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2685
reset_cache_read(&join_tab->cache);
2686
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2688
join_tab->readCachedRecord();
2689
if (!select || !select->skip_record())
2693
rc= (join_tab->next_select)(join,join_tab+1,0);
2694
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2696
reset_cache_write(&join_tab->cache);
2701
return NESTED_LOOP_ERROR;
2705
} while (!(error=info->read_record(info)));
2708
join_tab->readCachedRecord(); // Restore current record
2709
reset_cache_write(&join_tab->cache);
2710
if (error > 0) // Fatal error
2711
return NESTED_LOOP_ERROR;
2712
for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2713
tmp2->table->status=tmp2->status;
2714
return NESTED_LOOP_OK;
2717
/*****************************************************************************
2719
Functions that end one nested loop iteration. Different functions
2720
are used to support GROUP BY clause and to redirect records
2721
to a table (e.g. in case of SELECT into a temporary table) or to the
2725
NESTED_LOOP_OK - the record has been successfully handled
2726
NESTED_LOOP_ERROR - a fatal error (like table corruption)
2728
NESTED_LOOP_KILLED - thread shutdown was requested while processing
2730
NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;
2731
additionally, the nested loop produced the
2732
number of rows specified in the LIMIT clause
2734
NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
2735
additionally, there is a cursor and the nested
2736
loop algorithm produced the number of rows
2737
that is specified for current cursor fetch
2739
All return values except NESTED_LOOP_OK abort the nested loop.
2740
*****************************************************************************/
2741
enum_nested_loop_state end_send(JOIN *join, JoinTable *, bool end_of_records)
2743
if (! end_of_records)
2746
if (join->having && join->having->val_int() == 0)
2747
return NESTED_LOOP_OK; // Didn't match having
2749
if (join->do_send_rows)
2750
error=join->result->send_data(*join->fields);
2752
return NESTED_LOOP_ERROR;
2753
if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2755
if (join->select_options & OPTION_FOUND_ROWS)
2757
JoinTable *jt=join->join_tab;
2758
if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2759
&& !join->send_group_parts && !join->having && !jt->select_cond &&
2760
!(jt->select && jt->select->quick) &&
2761
(jt->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
2764
/* Join over all rows in table; Return number of found rows */
2765
Table *table= jt->table;
2767
join->select_options^= OPTION_FOUND_ROWS;
2768
if (table->sort.record_pointers ||
2769
(table->sort.io_cache && my_b_inited(table->sort.io_cache)))
2771
/* Using filesort */
2772
join->send_records= table->sort.found_records;
2776
table->cursor->info(HA_STATUS_VARIABLE);
2777
join->send_records= table->cursor->stats.records;
2782
join->do_send_rows= 0;
2783
if (join->unit->fake_select_lex)
2784
join->unit->fake_select_lex->select_limit= 0;
2785
return NESTED_LOOP_OK;
2788
return NESTED_LOOP_QUERY_LIMIT; // Abort nicely
2790
else if (join->send_records >= join->fetch_limit)
2793
There is a server side cursor and all rows for
2794
this fetch request are sent.
2796
return NESTED_LOOP_CURSOR_LIMIT;
2800
return NESTED_LOOP_OK;
2803
enum_nested_loop_state end_write(JOIN *join, JoinTable *, bool end_of_records)
2805
Table *table= join->tmp_table;
2807
if (join->session->killed) // Aborted by user
2809
join->session->send_kill_message();
2810
return NESTED_LOOP_KILLED;
2812
if (!end_of_records)
2814
copy_fields(&join->tmp_table_param);
2815
copy_funcs(join->tmp_table_param.items_to_copy);
2816
if (!join->having || join->having->val_int())
2819
join->found_records++;
2820
if ((error=table->cursor->ha_write_row(table->record[0])))
2822
if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))
2824
if (create_myisam_from_heap(join->session, table,
2825
join->tmp_table_param.start_recinfo,
2826
&join->tmp_table_param.recinfo,
2828
return NESTED_LOOP_ERROR; // Not a table_is_full error
2829
table->s->uniques= 0; // To ensure rows are the same
2831
if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
2833
if (!(join->select_options & OPTION_FOUND_ROWS))
2834
return NESTED_LOOP_QUERY_LIMIT;
2835
join->do_send_rows= 0;
2836
join->unit->select_limit_cnt= HA_POS_ERROR;
2837
return NESTED_LOOP_OK;
2842
return NESTED_LOOP_OK;
2845
/** Group by searching after group record and updating it if possible. */
2846
enum_nested_loop_state end_update(JOIN *join, JoinTable *, bool end_of_records)
2848
Table *table= join->tmp_table;
2853
return NESTED_LOOP_OK;
2854
if (join->session->killed) // Aborted by user
2856
join->session->send_kill_message();
2857
return NESTED_LOOP_KILLED;
2860
join->found_records++;
2861
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2862
/* Make a key of group index */
2863
for (group=table->group ; group ; group=group->next)
2865
Item *item= *group->item;
2866
item->save_org_in_field(group->field);
2867
/* Store in the used key if the field was 0 */
2868
if (item->maybe_null)
2869
group->buff[-1]= (char) group->field->is_null();
2871
if (!table->cursor->index_read_map(table->record[1],
2872
join->tmp_table_param.group_buff,
2875
{ /* Update old record */
2876
table->restoreRecord();
2877
update_tmptable_sum_func(join->sum_funcs,table);
2878
if ((error= table->cursor->ha_update_row(table->record[1],
2881
table->print_error(error,MYF(0));
2882
return NESTED_LOOP_ERROR;
2884
return NESTED_LOOP_OK;
2888
Copy null bits from group key to table
2889
We can't copy all data as the key may have different format
2890
as the row data (for example as with VARCHAR keys)
2892
KEY_PART_INFO *key_part;
2893
for (group=table->group,key_part=table->key_info[0].key_part;
2895
group=group->next,key_part++)
2897
if (key_part->null_bit)
2898
memcpy(table->record[0]+key_part->offset, group->buff, 1);
2900
init_tmptable_sum_functions(join->sum_funcs);
2901
copy_funcs(join->tmp_table_param.items_to_copy);
2902
if ((error=table->cursor->ha_write_row(table->record[0])))
2904
if (create_myisam_from_heap(join->session, table,
2905
join->tmp_table_param.start_recinfo,
2906
&join->tmp_table_param.recinfo,
2908
return NESTED_LOOP_ERROR; // Not a table_is_full error
2909
/* Change method to update rows */
2910
table->cursor->ha_index_init(0, 0);
2911
join->join_tab[join->tables-1].next_select= end_unique_update;
2913
join->send_records++;
2914
return NESTED_LOOP_OK;
2917
/** Like end_update, but this is done with unique constraints instead of keys. */
2918
enum_nested_loop_state end_unique_update(JOIN *join, JoinTable *, bool end_of_records)
2920
Table *table= join->tmp_table;
2924
return NESTED_LOOP_OK;
2925
if (join->session->killed) // Aborted by user
2927
join->session->send_kill_message();
2928
return NESTED_LOOP_KILLED;
2931
init_tmptable_sum_functions(join->sum_funcs);
2932
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2933
copy_funcs(join->tmp_table_param.items_to_copy);
2935
if (!(error= table->cursor->ha_write_row(table->record[0])))
2936
join->send_records++; // New group
2939
if ((int) table->get_dup_key(error) < 0)
2941
table->print_error(error,MYF(0));
2942
return NESTED_LOOP_ERROR;
2944
if (table->cursor->rnd_pos(table->record[1],table->cursor->dup_ref))
2946
table->print_error(error,MYF(0));
2947
return NESTED_LOOP_ERROR;
2949
table->restoreRecord();
2950
update_tmptable_sum_func(join->sum_funcs,table);
2951
if ((error= table->cursor->ha_update_row(table->record[1],
2954
table->print_error(error,MYF(0));
2955
return NESTED_LOOP_ERROR;
2958
return NESTED_LOOP_OK;
2962
allocate group fields or take prepared (cached).
2964
@param main_join join of current select
2965
@param curr_join current join (join of current select or temporary copy
2973
static bool make_group_fields(JOIN *main_join, JOIN *curr_join)
2975
if (main_join->group_fields_cache.elements)
2977
curr_join->group_fields= main_join->group_fields_cache;
2978
curr_join->sort_and_group= 1;
2982
if (alloc_group_fields(curr_join, curr_join->group_list))
2984
main_join->group_fields_cache= curr_join->group_fields;
2990
calc how big buffer we need for comparing group entries.
2992
static void calc_group_buffer(JOIN *join,order_st *group)
2994
uint32_t key_length=0, parts=0, null_parts=0;
2998
for (; group ; group=group->next)
3000
Item *group_item= *group->item;
3001
Field *field= group_item->get_tmp_table_field();
3004
enum_field_types type;
3005
if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
3006
key_length+=MAX_BLOB_WIDTH; // Can't be used as a key
3007
else if (type == DRIZZLE_TYPE_VARCHAR)
3008
key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
3010
key_length+= field->pack_length();
3014
switch (group_item->result_type()) {
3016
key_length+= sizeof(double);
3019
key_length+= sizeof(int64_t);
3021
case DECIMAL_RESULT:
3022
key_length+= my_decimal_get_binary_size(group_item->max_length -
3023
(group_item->decimals ? 1 : 0),
3024
group_item->decimals);
3028
enum enum_field_types type= group_item->field_type();
3030
As items represented as DATE/TIME fields in the group buffer
3031
have STRING_RESULT result type, we increase the length
3032
by 8 as maximum pack length of such fields.
3034
if (type == DRIZZLE_TYPE_DATE ||
3035
type == DRIZZLE_TYPE_DATETIME ||
3036
type == DRIZZLE_TYPE_TIMESTAMP)
3043
Group strings are taken as varstrings and require an length field.
3044
A field is not yet created by create_tmp_field()
3045
and the sizes should match up.
3047
key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3052
/* This case should never be choosen */
3054
my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
3058
if (group_item->maybe_null)
3061
join->tmp_table_param.group_length=key_length+null_parts;
3062
join->tmp_table_param.group_parts=parts;
3063
join->tmp_table_param.group_null_parts=null_parts;
3067
Get a list of buffers for saveing last group.
3069
Groups are saved in reverse order for easyer check loop.
3071
static bool alloc_group_fields(JOIN *join,order_st *group)
3075
for (; group ; group=group->next)
3077
Cached_item *tmp= new_Cached_item(join->session, *group->item);
3078
if (!tmp || join->group_fields.push_front(tmp))
3082
join->sort_and_group=1; /* Mark for do_select */
3086
static uint32_t cache_record_length(JOIN *join,uint32_t idx)
3089
JoinTable **pos,**end;
3090
Session *session=join->session;
3092
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
3096
JoinTable *join_tab= *pos;
3097
if (!join_tab->used_fieldlength) /* Not calced yet */
3098
calc_used_field_length(session, join_tab);
3099
length+=join_tab->used_fieldlength;
3105
Get the number of different row combinations for subset of partial join
3109
join The join structure
3110
idx Number of tables in the partial join order (i.e. the
3111
partial join order is in join->positions[0..idx-1])
3112
found_ref Bitmap of tables for which we need to find # of distinct
3116
Given a partial join order (in join->positions[0..idx-1]) and a subset of
3117
tables within that join order (specified in found_ref), find out how many
3118
distinct row combinations of subset tables will be in the result of the
3121
This is used as follows: Suppose we have a table accessed with a ref-based
3122
method. The ref access depends on current rows of tables in found_ref.
3123
We want to count # of different ref accesses. We assume two ref accesses
3124
will be different if at least one of access parameters is different.
3125
Example: consider a query
3127
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
3130
t1, ref access on t1.key=c1
3131
t2, ref access on t2.key=c2
3132
t3, ref access on t3.key=t1.field
3134
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
3135
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
3136
For t3: n_ref_scans = records_read(t1)*records_read(t2)
3137
n_distinct_ref_scans = #records_read(t1)
3139
The reason for having this function (at least the latest version of it)
3140
is that we need to account for buffering in join execution.
3142
An edge-case example: if we have a non-first table in join accessed via
3143
ref(const) or ref(param) where there is a small number of different
3144
values of param, then the access will likely hit the disk cache and will
3145
not require any disk seeks.
3147
The proper solution would be to assume an LRU disk cache of some size,
3148
calculate probability of cache hits, etc. For now we just count
3149
identical ref accesses as one.
3152
Expected number of row combinations
3154
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
3157
optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3158
for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1);
3162
if (pos->examinePosition(found_ref))
3164
found_ref|= pos->getRefDependMap();
3166
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
3167
with no matching row we will get position[t2].records_read==0.
3168
Actually the size of output is one null-complemented row, therefore
3169
we will use value of 1 whenever we get records_read==0.
3172
- the above case can't occur if inner part of outer join has more
3173
than one table: table with no matches will not be marked as const.
3175
- Ideally we should add 1 to records_read for every possible null-
3176
complemented row. We're not doing it because: 1. it will require
3177
non-trivial code and add overhead. 2. The value of records_read
3178
is an inprecise estimate and adding 1 (or, in the worst case,
3179
#max_nested_outer_joins=64-1) will not make it any more precise.
3181
if (pos->getFanout() > DBL_EPSILON)
3182
found*= pos->getFanout();
3189
Set up join struct according to best position.
3191
static bool get_best_combination(JOIN *join)
3194
table_map used_tables;
3195
JoinTable *join_tab,*j;
3196
optimizer::KeyUse *keyuse;
3197
uint32_t table_count;
3198
Session *session=join->session;
3199
optimizer::Position cur_pos;
3201
table_count=join->tables;
3202
if (!(join->join_tab=join_tab=
3203
(JoinTable*) session->alloc(sizeof(JoinTable)*table_count)))
3208
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
3209
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
3212
cur_pos= join->getPosFromOptimalPlan(tablenr);
3213
*j= *cur_pos.getJoinTable();
3214
form=join->table[tablenr]=j->table;
3215
used_tables|= form->map;
3216
form->reginfo.join_tab=j;
3217
if (!*j->on_expr_ref)
3218
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
3219
if (j->type == AM_CONST)
3220
continue; // Handled in make_join_stat..
3225
if (j->type == AM_SYSTEM)
3227
if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
3230
if (tablenr != join->const_tables)
3233
else if (create_ref_for_key(join, j, keyuse, used_tables))
3234
return(true); // Something went wrong
3237
for (i=0 ; i < table_count ; i++)
3238
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
3239
update_depend_map(join);
3243
/** Save const tables first as used tables. */
3244
static void set_position(JOIN *join,
3247
optimizer::KeyUse *key)
3249
optimizer::Position tmp_pos(1.0, /* This is a const table */
3254
join->setPosInPartialPlan(idx, tmp_pos);
3256
/* Move the const table as down as possible in best_ref */
3257
JoinTable **pos=join->best_ref+idx+1;
3258
JoinTable *next=join->best_ref[idx];
3259
for (;next != table ; pos++)
3261
JoinTable *tmp=pos[0];
3265
join->best_ref[idx]=table;
3269
Selects and invokes a search strategy for an optimal query plan.
3271
The function checks user-configurable parameters that control the search
3272
strategy for an optimal plan, selects the search method and then invokes
3273
it. Each specific optimization procedure stores the final optimal plan in
3274
the array 'join->best_positions', and the cost of the plan in
3277
@param join pointer to the structure providing all context info for
3279
@param join_tables set of the tables in the query
3286
static bool choose_plan(JOIN *join, table_map join_tables)
3288
uint32_t search_depth= join->session->variables.optimizer_search_depth;
3289
uint32_t prune_level= join->session->variables.optimizer_prune_level;
3290
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
3292
join->cur_embedding_map.reset();
3293
reset_nj_counters(join->join_list);
3295
if (SELECT_STRAIGHT_JOIN option is set)
3296
reorder tables so dependent tables come after tables they depend
3297
on, otherwise keep tables in the order they were specified in the query
3299
Apply heuristic: pre-sort all access plans with respect to the number of
3302
internal::my_qsort(join->best_ref + join->const_tables,
3303
join->tables - join->const_tables, sizeof(JoinTable*),
3304
straight_join ? join_tab_cmp_straight : join_tab_cmp);
3307
optimize_straight_join(join, join_tables);
3311
if (search_depth == 0)
3312
/* Automatically determine a reasonable value for 'search_depth' */
3313
search_depth= determine_search_depth(join);
3314
if (greedy_search(join, join_tables, search_depth, prune_level))
3319
Store the cost of this query into a user variable
3320
Don't update last_query_cost for statements that are not "flat joins" :
3321
i.e. they have subqueries, unions or call stored procedures.
3322
TODO: calculate a correct cost for a query with subqueries and UNIONs.
3324
if (join->session->lex->is_single_level_stmt())
3325
join->session->status_var.last_query_cost= join->best_read;
3330
Find the best access path for an extension of a partial execution
3331
plan and add this path to the plan.
3333
The function finds the best access path to table 's' from the passed
3334
partial plan where an access path is the general term for any means to
3335
access the data in 's'. An access path may use either an index or a scan,
3336
whichever is cheaper. The input partial plan is passed via the array
3337
'join->positions' of length 'idx'. The chosen access method for 's' and its
3338
cost are stored in 'join->positions[idx]'.
3340
@param join pointer to the structure providing all context info
3342
@param s the table to be joined by the function
3343
@param session thread for the connection that submitted the query
3344
@param remaining_tables set of tables not included into the partial plan yet
3345
@param idx the length of the partial plan
3346
@param record_count estimate for the number of records returned by the
3348
@param read_time the cost of the partial plan
3353
static void best_access_path(JOIN *join,
3356
table_map remaining_tables,
3358
double record_count,
3361
optimizer::KeyUse *best_key= NULL;
3362
uint32_t best_max_key_part= 0;
3363
bool found_constraint= 0;
3364
double best= DBL_MAX;
3365
double best_time= DBL_MAX;
3366
double records= DBL_MAX;
3367
table_map best_ref_depends_map= 0;
3372
{ /* Use key if possible */
3373
Table *table= s->table;
3374
optimizer::KeyUse *keyuse= NULL;
3375
optimizer::KeyUse *start_key= NULL;
3376
double best_records= DBL_MAX;
3377
uint32_t max_key_part=0;
3379
/* Test how we can use keys */
3380
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
3381
for (keyuse= s->keyuse; keyuse->getTable() == table; )
3383
key_part_map found_part= 0;
3384
table_map found_ref= 0;
3385
uint32_t key= keyuse->getKey();
3386
KEY *keyinfo= table->key_info + key;
3387
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
3388
key_part_map const_part= 0;
3389
/* The or-null keypart in ref-or-null access: */
3390
key_part_map ref_or_null_part= 0;
3392
/* Calculate how many key segments of the current key we can use */
3395
do /* For each keypart */
3397
uint32_t keypart= keyuse->getKeypart();
3398
table_map best_part_found_ref= 0;
3399
double best_prev_record_reads= DBL_MAX;
3401
do /* For each way to access the keypart */
3405
if 1. expression doesn't refer to forward tables
3406
2. we won't get two ref-or-null's
3408
if (! (remaining_tables & keyuse->getUsedTables()) &&
3409
! (ref_or_null_part && (keyuse->getOptimizeFlags() &
3410
KEY_OPTIMIZE_REF_OR_NULL)))
3412
found_part|= keyuse->getKeypartMap();
3413
if (! (keyuse->getUsedTables() & ~join->const_table_map))
3414
const_part|= keyuse->getKeypartMap();
3416
double tmp2= prev_record_reads(join, idx, (found_ref |
3417
keyuse->getUsedTables()));
3418
if (tmp2 < best_prev_record_reads)
3420
best_part_found_ref= keyuse->getUsedTables() & ~join->const_table_map;
3421
best_prev_record_reads= tmp2;
3423
if (rec > keyuse->getTableRows())
3424
rec= keyuse->getTableRows();
3426
If there is one 'key_column IS NULL' expression, we can
3427
use this ref_or_null optimisation of this field
3429
if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)
3430
ref_or_null_part|= keyuse->getKeypartMap();
3434
} while (keyuse->getTable() == table && keyuse->getKey() == key &&
3435
keyuse->getKeypart() == keypart);
3436
found_ref|= best_part_found_ref;
3437
} while (keyuse->getTable() == table && keyuse->getKey() == key);
3440
Assume that that each key matches a proportional part of table.
3443
continue; // Nothing usable found
3445
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
3446
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
3449
found_constraint= 1;
3452
Check if we found full key
3454
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
3457
max_key_part= UINT32_MAX;
3458
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
3460
tmp = prev_record_reads(join, idx, found_ref);
3466
{ /* We found a const key */
3468
ReuseRangeEstimateForRef-1:
3469
We get here if we've found a ref(const) (c_i are constants):
3470
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
3472
If range optimizer was able to construct a "range"
3473
access on this index, then its condition "quick_cond" was
3474
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
3475
from the range optimizer.
3477
Proof of (*): By properties of range and ref optimizers
3478
quick_cond will be equal or tighther than ref_const_cond.
3479
ref_const_cond already covers "smallest" possible interval -
3480
a singlepoint interval over all keyparts. Therefore,
3481
quick_cond is equivalent to ref_const_cond (if it was an
3482
empty interval we wouldn't have got here).
3484
if (table->quick_keys.test(key))
3485
records= (double) table->quick_rows[key];
3488
/* quick_range couldn't use key! */
3489
records= (double) s->records/rec;
3494
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
3495
{ /* Prefer longer keys */
3497
((double) s->records / (double) rec *
3499
((double) (table->s->max_key_length-keyinfo->key_length) /
3500
(double) table->s->max_key_length)));
3502
records=2.0; /* Can't be as good as a unique */
3505
ReuseRangeEstimateForRef-2: We get here if we could not reuse
3506
E(#rows) from range optimizer. Make another try:
3508
If range optimizer produced E(#rows) for a prefix of the ref
3509
access we're considering, and that E(#rows) is lower then our
3510
current estimate, make an adjustment. The criteria of when we
3511
can make an adjustment is a special case of the criteria used
3512
in ReuseRangeEstimateForRef-3.
3514
if (table->quick_keys.test(key) &&
3515
const_part & (1 << table->quick_key_parts[key]) &&
3516
table->quick_n_ranges[key] == 1 &&
3517
records > (double) table->quick_rows[key])
3519
records= (double) table->quick_rows[key];
3522
/* Limit the number of matched rows */
3524
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3525
if (table->covering_keys.test(key))
3527
/* we can use only index tree */
3528
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3531
tmp= record_count * min(tmp,s->worst_seeks);
3537
Use as much key-parts as possible and a uniq key is better
3538
than a not unique key
3539
Set tmp to (previous record count) * (records / combination)
3541
if ((found_part & 1) &&
3542
(!(table->index_flags(key) & HA_ONLY_WHOLE_INDEX) ||
3543
found_part == PREV_BITS(uint, keyinfo->key_parts)))
3545
max_key_part= max_part_bit(found_part);
3547
ReuseRangeEstimateForRef-3:
3548
We're now considering a ref[or_null] access via
3549
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
3550
(same-as-above but with one cond replaced
3551
with "t.keypart_i IS NULL")] (**)
3553
Try re-using E(#rows) from "range" optimizer:
3554
We can do so if "range" optimizer used the same intervals as
3555
in (**). The intervals used by range optimizer may be not
3556
available at this point (as "range" access might have choosen to
3557
create quick select over another index), so we can't compare
3558
them to (**). We'll make indirect judgements instead.
3559
The sufficient conditions for re-use are:
3560
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
3561
this is not satisfied we have no way to know which ranges
3562
will be actually scanned by 'ref' until we execute the
3564
(C2) max #key parts in 'range' access == K == max_key_part (this
3565
is apparently a necessary requirement)
3567
We also have a property that "range optimizer produces equal or
3568
tighter set of scan intervals than ref(const) optimizer". Each
3569
of the intervals in (**) are "tightest possible" intervals when
3570
one limits itself to using keyparts 1..K (which we do in #2).
3571
From here it follows that range access used either one, or
3572
both of the (I1) and (I2) intervals:
3574
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
3575
(same-as-above but with one cond replaced
3576
with "t.keypart_i IS NULL") (I2)
3578
The remaining part is to exclude the situation where range
3579
optimizer used one interval while we're considering
3580
ref-or-null and looking for estimate for two intervals. This
3581
is done by last limitation:
3583
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
3585
if (table->quick_keys.test(key) && !found_ref && //(C1)
3586
table->quick_key_parts[key] == max_key_part && //(C2)
3587
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
3589
tmp= records= (double) table->quick_rows[key];
3593
/* Check if we have statistic about the distribution */
3594
if ((records= keyinfo->rec_per_key[max_key_part-1]))
3597
Fix for the case where the index statistics is too
3599
(1) We're considering ref(const) and there is quick select
3601
(2) and that quick select uses more keyparts (i.e. it will
3602
scan equal/smaller interval then this ref(const))
3603
(3) and E(#rows) for quick select is higher then our
3606
We'll use E(#rows) from quick select.
3608
Q: Why do we choose to use 'ref'? Won't quick select be
3609
cheaper in some cases ?
3610
TODO: figure this out and adjust the plan choice if needed.
3612
if (!found_ref && table->quick_keys.test(key) && // (1)
3613
table->quick_key_parts[key] > max_key_part && // (2)
3614
records < (double)table->quick_rows[key]) // (3)
3615
records= (double)table->quick_rows[key];
3622
Assume that the first key part matches 1% of the cursor
3623
and that the whole key matches 10 (duplicates) or 1
3625
Assume also that more key matches proportionally more
3627
This gives the formula:
3628
records = (x * (b-a) + a*c-b)/(c-1)
3630
b = records matched by whole key
3631
a = records matched by first key part (1% of all records?)
3632
c = number of key parts in key
3633
x = used key parts (1 <= x <= c)
3636
if (!(rec_per_key=(double)
3637
keyinfo->rec_per_key[keyinfo->key_parts-1]))
3638
rec_per_key=(double) s->records/rec+1;
3642
else if (rec_per_key/(double) s->records >= 0.01)
3646
double a=s->records*0.01;
3647
if (keyinfo->key_parts > 1)
3648
tmp= (max_key_part * (rec_per_key - a) +
3649
a*keyinfo->key_parts - rec_per_key)/
3650
(keyinfo->key_parts-1);
3653
set_if_bigger(tmp,1.0);
3655
records = (uint32_t) tmp;
3658
if (ref_or_null_part)
3660
/* We need to do two key searches to find key */
3666
ReuseRangeEstimateForRef-4: We get here if we could not reuse
3667
E(#rows) from range optimizer. Make another try:
3669
If range optimizer produced E(#rows) for a prefix of the ref
3670
access we're considering, and that E(#rows) is lower then our
3671
current estimate, make the adjustment.
3673
The decision whether we can re-use the estimate from the range
3674
optimizer is the same as in ReuseRangeEstimateForRef-3,
3675
applied to first table->quick_key_parts[key] key parts.
3677
if (table->quick_keys.test(key) &&
3678
table->quick_key_parts[key] <= max_key_part &&
3679
const_part & (1 << table->quick_key_parts[key]) &&
3680
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
3681
const_part) ? 1 : 0) &&
3682
records > (double) table->quick_rows[key])
3684
tmp= records= (double) table->quick_rows[key];
3688
/* Limit the number of matched rows */
3689
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3690
if (table->covering_keys.test(key))
3692
/* we can use only index tree */
3693
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3696
tmp= record_count * min(tmp,s->worst_seeks);
3699
tmp= best_time; // Do nothing
3703
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
3705
best_time= tmp + records/(double) TIME_FOR_COMPARE;
3707
best_records= records;
3708
best_key= start_key;
3709
best_max_key_part= max_key_part;
3710
best_ref_depends_map= found_ref;
3713
records= best_records;
3717
Don't test table scan if it can't be better.
3718
Prefer key lookup if we would use the same key for scanning.
3720
Don't do a table scan on InnoDB tables, if we can read the used
3721
parts of the row from any of the used index.
3722
This is because table scans uses index and we would not win
3723
anything by using a table scan.
3725
A word for word translation of the below if-statement in sergefp's
3726
understanding: we check if we should use table scan if:
3727
(1) The found 'ref' access produces more records than a table scan
3728
(or index scan, or quick select), or 'ref' is more expensive than
3730
(2) This doesn't hold: the best way to perform table scan is to to perform
3731
'range' access using index IDX, and the best way to perform 'ref'
3732
access is to use the same index IDX, with the same or more key parts.
3733
(note: it is not clear how this rule is/should be extended to
3734
index_merge quick selects)
3735
(3) See above note about InnoDB.
3736
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
3737
path, but there is no quick select)
3738
If the condition in the above brackets holds, then the only possible
3739
"table scan" access method is ALL/index (there is no quick select).
3740
Since we have a 'ref' access path, and FORCE INDEX instructs us to
3741
choose it over ALL/index, there is no need to consider a full table
3744
if ((records >= s->found_records || best > s->read_time) && // (1)
3745
! (s->quick && best_key && s->quick->index == best_key->getKey() && // (2)
3746
best_max_key_part >= s->table->quick_key_parts[best_key->getKey()]) &&// (2)
3747
! ((s->table->cursor->getEngine()->check_flag(HTON_BIT_TABLE_SCAN_ON_INDEX)) && // (3)
3748
! s->table->covering_keys.none() && best_key && !s->quick) && // (3)
3749
! (s->table->force_index && best_key && !s->quick)) // (4)
3750
{ // Check full join
3751
ha_rows rnd_records= s->found_records;
3753
If there is a filtering condition on the table (i.e. ref analyzer found
3754
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
3755
preceding this table in the join order we're now considering), then
3756
assume that 25% of the rows will be filtered out by this condition.
3758
This heuristic is supposed to force tables used in exprZ to be before
3759
this table in join order.
3761
if (found_constraint)
3762
rnd_records-= rnd_records/4;
3765
If applicable, get a more accurate estimate. Don't use the two
3768
if (s->table->quick_condition_rows != s->found_records)
3769
rnd_records= s->table->quick_condition_rows;
3772
Range optimizer never proposes a RANGE if it isn't better
3773
than FULL: so if RANGE is present, it's always preferred to FULL.
3774
Here we estimate its cost.
3780
- read record range through 'quick'
3781
- skip rows which does not satisfy WHERE constraints
3783
We take into account possible use of join cache for ALL/index
3784
access (see first else-branch below), but we don't take it into
3785
account here for range/index_merge access. Find out why this is so.
3788
(s->quick->read_time +
3789
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
3793
/* Estimate cost of reading table. */
3794
tmp= s->table->cursor->scan_time();
3795
if (s->table->map & join->outer_join) // Can't use join cache
3798
For each record we have to:
3799
- read the whole table record
3800
- skip rows which does not satisfy join condition
3804
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
3808
/* We read the table as many times as join buffer becomes full. */
3809
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
3811
(double) session->variables.join_buff_size));
3813
We don't make full cartesian product between rows in the scanned
3814
table and existing records because we skip all rows from the
3815
scanned table, which does not satisfy join condition when
3816
we read the table (see flush_cached_records for details). Here we
3817
take into account cost to read and skip these records.
3819
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
3824
We estimate the cost of evaluating WHERE clause for found records
3825
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
3826
tmp give us total cost of using Table SCAN
3828
if (best == DBL_MAX ||
3829
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
3830
best + record_count/(double) TIME_FOR_COMPARE*records))
3833
If the table has a range (s->quick is set) make_join_select()
3834
will ensure that this will be used
3837
records= rows2double(rnd_records);
3839
/* range/index_merge/ALL/index access method are "independent", so: */
3840
best_ref_depends_map= 0;
3844
/* Update the cost information for the current partial plan */
3845
optimizer::Position tmp_pos(records,
3849
best_ref_depends_map);
3850
join->setPosInPartialPlan(idx, tmp_pos);
3853
idx == join->const_tables &&
3854
s->table == join->sort_by_table &&
3855
join->unit->select_limit_cnt >= records)
3856
join->sort_by_table= (Table*) 1; // Must use temporary table
3862
Select the best ways to access the tables in a query without reordering them.
3864
Find the best access paths for each query table and compute their costs
3865
according to their order in the array 'join->best_ref' (thus without
3866
reordering the join tables). The function calls sequentially
3867
'best_access_path' for each table in the query to select the best table
3868
access method. The final optimal plan is stored in the array
3869
'join->best_positions', and the corresponding cost in 'join->best_read'.
3871
@param join pointer to the structure providing all context info for
3873
@param join_tables set of the tables in the query
3876
This function can be applied to:
3877
- queries with STRAIGHT_JOIN
3878
- internally to compute the cost of an arbitrary QEP
3880
Thus 'optimize_straight_join' can be used at any stage of the query
3881
optimization process to finalize a QEP as it is.
3883
static void optimize_straight_join(JOIN *join, table_map join_tables)
3886
optimizer::Position partial_pos;
3887
uint32_t idx= join->const_tables;
3888
double record_count= 1.0;
3889
double read_time= 0.0;
3891
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
3893
/* Find the best access method from 's' to the current partial plan */
3894
best_access_path(join, s, join->session, join_tables, idx,
3895
record_count, read_time);
3896
/* compute the cost of the new plan extended with 's' */
3897
partial_pos= join->getPosFromPartialPlan(idx);
3898
record_count*= partial_pos.getFanout();
3899
read_time+= partial_pos.getCost();
3900
join_tables&= ~(s->table->map);
3904
read_time+= record_count / (double) TIME_FOR_COMPARE;
3905
partial_pos= join->getPosFromPartialPlan(join->const_tables);
3906
if (join->sort_by_table &&
3907
partial_pos.hasTableForSorting(join->sort_by_table))
3908
read_time+= record_count; // We have to make a temp table
3909
join->copyPartialPlanIntoOptimalPlan(idx);
3910
join->best_read= read_time;
3914
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
3916
The search procedure uses a hybrid greedy/exhaustive search with controlled
3917
exhaustiveness. The search is performed in N = card(remaining_tables)
3918
steps. Each step evaluates how promising is each of the unoptimized tables,
3919
selects the most promising table, and extends the current partial QEP with
3920
that table. Currenly the most 'promising' table is the one with least
3921
expensive extension.\
3923
There are two extreme cases:
3924
-# When (card(remaining_tables) < search_depth), the estimate finds the
3925
best complete continuation of the partial QEP. This continuation can be
3926
used directly as a result of the search.
3927
-# When (search_depth == 1) the 'best_extension_by_limited_search'
3928
consideres the extension of the current QEP with each of the remaining
3931
All other cases are in-between these two extremes. Thus the parameter
3932
'search_depth' controlls the exhaustiveness of the search. The higher the
3933
value, the longer the optimizaton time and possibly the better the
3934
resulting plan. The lower the value, the fewer alternative plans are
3935
estimated, but the more likely to get a bad QEP.
3937
All intermediate and final results of the procedure are stored in 'join':
3938
- join->positions : modified for every partial QEP that is explored
3939
- join->best_positions: modified for the current best complete QEP
3940
- join->best_read : modified for the current best complete QEP
3941
- join->best_ref : might be partially reordered
3943
The final optimal plan is stored in 'join->best_positions', and its
3944
corresponding cost in 'join->best_read'.
3947
The following pseudocode describes the algorithm of 'greedy_search':
3950
procedure greedy_search
3951
input: remaining_tables
3956
(t, a) = best_extension(pplan, remaining_tables);
3957
pplan = concat(pplan, (t, a));
3958
remaining_tables = remaining_tables - t;
3959
} while (remaining_tables != {})
3964
where 'best_extension' is a placeholder for a procedure that selects the
3965
most "promising" of all tables in 'remaining_tables'.
3966
Currently this estimate is performed by calling
3967
'best_extension_by_limited_search' to evaluate all extensions of the
3968
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
3969
mainly depends on that of 'best_extension_by_limited_search'.
3972
If 'best_extension()' == 'best_extension_by_limited_search()', then the
3973
worst-case complexity of this algorithm is <=
3974
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
3975
complexity of greedy_search is O(N!).
3978
In the future, 'greedy_search' might be extended to support other
3979
implementations of 'best_extension', e.g. some simpler quadratic procedure.
3981
@param join pointer to the structure providing all context info
3983
@param remaining_tables set of tables not included into the partial plan yet
3984
@param search_depth controlls the exhaustiveness of the search
3985
@param prune_level the pruning heuristics that should be applied during
3993
static bool greedy_search(JOIN *join,
3994
table_map remaining_tables,
3995
uint32_t search_depth,
3996
uint32_t prune_level)
3998
double record_count= 1.0;
3999
double read_time= 0.0;
4000
uint32_t idx= join->const_tables; // index into 'join->best_ref'
4002
uint32_t size_remain; // cardinality of remaining_tables
4003
optimizer::Position best_pos;
4004
JoinTable *best_table; // the next plan node to be added to the curr QEP
4006
/* number of tables that remain to be optimized */
4007
size_remain= internal::my_count_bits(remaining_tables);
4010
/* Find the extension of the current QEP with the lowest cost */
4011
join->best_read= DBL_MAX;
4012
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
4013
read_time, search_depth, prune_level))
4016
if (size_remain <= search_depth)
4019
'join->best_positions' contains a complete optimal extension of the
4020
current partial QEP.
4025
/* select the first table in the optimal extension as most promising */
4026
best_pos= join->getPosFromOptimalPlan(idx);
4027
best_table= best_pos.getJoinTable();
4029
Each subsequent loop of 'best_extension_by_limited_search' uses
4030
'join->positions' for cost estimates, therefore we have to update its
4033
join->setPosInPartialPlan(idx, best_pos);
4035
/* find the position of 'best_table' in 'join->best_ref' */
4037
JoinTable *pos= join->best_ref[best_idx];
4038
while (pos && best_table != pos)
4039
pos= join->best_ref[++best_idx];
4040
assert((pos != NULL)); // should always find 'best_table'
4041
/* move 'best_table' at the first free position in the array of joins */
4042
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
4044
/* compute the cost of the new plan extended with 'best_table' */
4045
optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
4046
record_count*= partial_pos.getFanout();
4047
read_time+= partial_pos.getCost();
4049
remaining_tables&= ~(best_table->table->map);
4057
Find a good, possibly optimal, query execution plan (QEP) by a possibly
4060
The procedure searches for the optimal ordering of the query tables in set
4061
'remaining_tables' of size N, and the corresponding optimal access paths to
4062
each table. The choice of a table order and an access path for each table
4063
constitutes a query execution plan (QEP) that fully specifies how to
4066
The maximal size of the found plan is controlled by the parameter
4067
'search_depth'. When search_depth == N, the resulting plan is complete and
4068
can be used directly as a QEP. If search_depth < N, the found plan consists
4069
of only some of the query tables. Such "partial" optimal plans are useful
4070
only as input to query optimization procedures, and cannot be used directly
4073
The algorithm begins with an empty partial plan stored in 'join->positions'
4074
and a set of N tables - 'remaining_tables'. Each step of the algorithm
4075
evaluates the cost of the partial plan extended by all access plans for
4076
each of the relations in 'remaining_tables', expands the current partial
4077
plan with the access plan that results in lowest cost of the expanded
4078
partial plan, and removes the corresponding relation from
4079
'remaining_tables'. The algorithm continues until it either constructs a
4080
complete optimal plan, or constructs an optimal plartial plan with size =
4083
The final optimal plan is stored in 'join->best_positions'. The
4084
corresponding cost of the optimal plan is in 'join->best_read'.
4087
The procedure uses a recursive depth-first search where the depth of the
4088
recursion (and thus the exhaustiveness of the search) is controlled by the
4089
parameter 'search_depth'.
4092
The pseudocode below describes the algorithm of
4093
'best_extension_by_limited_search'. The worst-case complexity of this
4094
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
4095
the complexity of greedy_search is O(N!).
4098
procedure best_extension_by_limited_search(
4099
pplan in, // in, partial plan of tables-joined-so-far
4100
pplan_cost, // in, cost of pplan
4101
remaining_tables, // in, set of tables not referenced in pplan
4102
best_plan_so_far, // in/out, best plan found so far
4103
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
4104
search_depth) // in, maximum size of the plans being considered
4106
for each table T from remaining_tables
4108
// Calculate the cost of using table T as above
4109
cost = complex-series-of-calculations;
4111
// Add the cost to the cost so far.
4114
if (pplan_cost >= best_plan_so_far_cost)
4115
// pplan_cost already too great, stop search
4118
pplan= expand pplan by best_access_method;
4119
remaining_tables= remaining_tables - table T;
4120
if (remaining_tables is not an empty set
4124
best_extension_by_limited_search(pplan, pplan_cost,
4127
best_plan_so_far_cost,
4132
best_plan_so_far_cost= pplan_cost;
4133
best_plan_so_far= pplan;
4140
When 'best_extension_by_limited_search' is called for the first time,
4141
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
4142
The actual implementation provides a way to optionally use pruning
4143
heuristic (controlled by the parameter 'prune_level') to reduce the search
4144
space by skipping some partial plans.
4147
The parameter 'search_depth' provides control over the recursion
4148
depth, and thus the size of the resulting optimal plan.
4150
@param join pointer to the structure providing all context info
4152
@param remaining_tables set of tables not included into the partial plan yet
4153
@param idx length of the partial QEP in 'join->positions';
4154
since a depth-first search is used, also corresponds
4155
to the current depth of the search tree;
4156
also an index in the array 'join->best_ref';
4157
@param record_count estimate for the number of records returned by the
4159
@param read_time the cost of the best partial plan
4160
@param search_depth maximum depth of the recursion and thus size of the
4162
(0 < search_depth <= join->tables+1).
4163
@param prune_level pruning heuristics that should be applied during
4165
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
4172
static bool best_extension_by_limited_search(JOIN *join,
4173
table_map remaining_tables,
4175
double record_count,
4177
uint32_t search_depth,
4178
uint32_t prune_level)
4180
Session *session= join->session;
4181
if (session->killed) // Abort
4185
'join' is a partial plan with lower cost than the best plan so far,
4186
so continue expanding it further with the tables in 'remaining_tables'.
4189
double best_record_count= DBL_MAX;
4190
double best_read_time= DBL_MAX;
4191
optimizer::Position partial_pos;
4193
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4195
table_map real_table_bit= s->table->map;
4198
partial_pos= join->getPosFromPartialPlan(idx - 1);
4200
if ((remaining_tables & real_table_bit) &&
4201
! (remaining_tables & s->dependent) &&
4202
(! idx || ! check_interleaving_with_nj(partial_pos.getJoinTable(), s)))
4204
double current_record_count, current_read_time;
4207
psergey-insideout-todo:
4208
when best_access_path() detects it could do an InsideOut scan or
4209
some other scan, have it return an insideout scan and a flag that
4210
requests to "fork" this loop iteration. (Q: how does that behave
4211
when the depth is insufficient??)
4213
/* Find the best access method from 's' to the current partial plan */
4214
best_access_path(join, s, session, remaining_tables, idx,
4215
record_count, read_time);
4216
/* Compute the cost of extending the plan with 's' */
4217
partial_pos= join->getPosFromPartialPlan(idx);
4218
current_record_count= record_count * partial_pos.getFanout();
4219
current_read_time= read_time + partial_pos.getCost();
4221
/* Expand only partial plans with lower cost than the best QEP so far */
4222
if ((current_read_time +
4223
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
4225
restore_prev_nj_state(s);
4230
Prune some less promising partial plans. This heuristic may miss
4231
the optimal QEPs, thus it results in a non-exhaustive search.
4233
if (prune_level == 1)
4235
if (best_record_count > current_record_count ||
4236
best_read_time > current_read_time ||
4237
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
4239
if (best_record_count >= current_record_count &&
4240
best_read_time >= current_read_time &&
4241
/* TODO: What is the reasoning behind this condition? */
4242
(! (s->key_dependent & remaining_tables) ||
4243
partial_pos.isConstTable()))
4245
best_record_count= current_record_count;
4246
best_read_time= current_read_time;
4251
restore_prev_nj_state(s);
4256
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
4257
{ /* Recursively expand the current partial plan */
4258
std::swap(join->best_ref[idx], *pos);
4259
if (best_extension_by_limited_search(join,
4260
remaining_tables & ~real_table_bit,
4262
current_record_count,
4267
std::swap(join->best_ref[idx], *pos);
4271
'join' is either the best partial QEP with 'search_depth' relations,
4272
or the best complete QEP so far, whichever is smaller.
4274
partial_pos= join->getPosFromPartialPlan(join->const_tables);
4275
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4276
if (join->sort_by_table &&
4277
partial_pos.hasTableForSorting(join->sort_by_table))
4278
/* We have to make a temp table */
4279
current_read_time+= current_record_count;
4280
if ((search_depth == 1) || (current_read_time < join->best_read))
4282
join->copyPartialPlanIntoOptimalPlan(idx + 1);
4283
join->best_read= current_read_time - 0.001;
4286
restore_prev_nj_state(s);
4293
Heuristic procedure to automatically guess a reasonable degree of
4294
exhaustiveness for the greedy search procedure.
4296
The procedure estimates the optimization time and selects a search depth
4297
big enough to result in a near-optimal QEP, that doesn't take too long to
4298
find. If the number of tables in the query exceeds some constant, then
4299
search_depth is set to this constant.
4301
@param join pointer to the structure providing all context info for
4305
This is an extremely simplistic implementation that serves as a stub for a
4306
more advanced analysis of the join. Ideally the search depth should be
4307
determined by learning from previous query optimizations, because it will
4308
depend on the CPU power (and other factors).
4311
this value should be determined dynamically, based on statistics:
4312
uint32_t max_tables_for_exhaustive_opt= 7;
4315
this value could be determined by some mapping of the form:
4316
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4319
A positive integer that specifies the search depth (and thus the
4320
exhaustiveness) of the depth-first search algorithm used by
4323
static uint32_t determine_search_depth(JOIN *join)
4325
uint32_t table_count= join->tables - join->const_tables;
4326
uint32_t search_depth;
4327
/* TODO: this value should be determined dynamically, based on statistics: */
4328
uint32_t max_tables_for_exhaustive_opt= 7;
4330
if (table_count <= max_tables_for_exhaustive_opt)
4331
search_depth= table_count+1; // use exhaustive for small number of tables
4334
TODO: this value could be determined by some mapping of the form:
4335
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4337
search_depth= max_tables_for_exhaustive_opt; // use greedy search
4339
return search_depth;
4342
static bool make_simple_join(JOIN *join,Table *tmp_table)
4345
JoinTable *join_tab;
4348
Reuse Table * and JoinTable if already allocated by a previous call
4349
to this function through JOIN::exec (may happen for sub-queries).
4351
if (!join->table_reexec)
4353
if (!(join->table_reexec= (Table**) join->session->alloc(sizeof(Table*))))
4356
join->tmp_join->table_reexec= join->table_reexec;
4358
if (!join->join_tab_reexec)
4360
if (!(join->join_tab_reexec=
4361
(JoinTable*) join->session->alloc(sizeof(JoinTable))))
4364
join->tmp_join->join_tab_reexec= join->join_tab_reexec;
4366
tableptr= join->table_reexec;
4367
join_tab= join->join_tab_reexec;
4369
join->join_tab=join_tab;
4370
join->table=tableptr; tableptr[0]=tmp_table;
4372
join->const_tables=0;
4373
join->const_table_map=0;
4374
join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=
4375
join->tmp_table_param.func_count=0;
4376
join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;
4377
join->first_record=join->sort_and_group=0;
4378
join->send_records=(ha_rows) 0;
4380
join->row_limit=join->unit->select_limit_cnt;
4381
join->do_send_rows = (join->row_limit) ? 1 : 0;
4383
join_tab->cache.buff=0; /* No caching */
4384
join_tab->table=tmp_table;
4386
join_tab->select_cond=0;
4388
join_tab->type= AM_ALL; /* Map through all records */
4389
join_tab->keys.set(); /* test everything in quick */
4391
join_tab->on_expr_ref=0;
4392
join_tab->last_inner= 0;
4393
join_tab->first_unmatched= 0;
4394
join_tab->ref.key = -1;
4395
join_tab->not_used_in_distinct=0;
4396
join_tab->read_first_record= join_init_read_record;
4397
join_tab->join=join;
4398
join_tab->ref.key_parts= 0;
4399
memset(&join_tab->read_record, 0, sizeof(join_tab->read_record));
4400
tmp_table->status=0;
4401
tmp_table->null_row=0;
4406
Fill in outer join related info for the execution plan structure.
4408
For each outer join operation left after simplification of the
4409
original query the function set up the following pointers in the linear
4410
structure join->join_tab representing the selected execution plan.
4411
The first inner table t0 for the operation is set to refer to the last
4412
inner table tk through the field t0->last_inner.
4413
Any inner table ti for the operation are set to refer to the first
4414
inner table ti->first_inner.
4415
The first inner table t0 for the operation is set to refer to the
4416
first inner table of the embedding outer join operation, if there is any,
4417
through the field t0->first_upper.
4418
The on expression for the outer join operation is attached to the
4419
corresponding first inner table through the field t0->on_expr_ref.
4420
Here ti are structures of the JoinTable type.
4422
EXAMPLE. For the query:
4426
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
4427
ON (t1.a=t2.a AND t1.b=t3.b)
4431
given the execution plan with the table order t1,t2,t3,t4
4432
is selected, the following references will be set;
4433
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
4434
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
4435
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
4436
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
4438
@param join reference to the info fully describing the query
4441
The function assumes that the simplification procedure has been
4442
already applied to the join query (see simplify_joins).
4443
This function can be called only after the execution plan
4446
static void make_outerjoin_info(JOIN *join)
4448
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4450
JoinTable *tab=join->join_tab+i;
4451
Table *table=tab->table;
4452
TableList *tbl= table->pos_in_table_list;
4453
TableList *embedding= tbl->embedding;
4455
if (tbl->outer_join)
4458
Table tab is the only one inner table for outer join.
4459
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
4460
is in the query above.)
4462
tab->last_inner= tab->first_inner= tab;
4463
tab->on_expr_ref= &tbl->on_expr;
4464
tab->cond_equal= tbl->cond_equal;
4466
tab->first_upper= embedding->nested_join->first_nested;
4468
for ( ; embedding ; embedding= embedding->embedding)
4470
/* Ignore sj-nests: */
4471
if (!embedding->on_expr)
4473
nested_join_st *nested_join= embedding->nested_join;
4474
if (!nested_join->counter_)
4477
Table tab is the first inner table for nested_join.
4478
Save reference to it in the nested join structure.
4480
nested_join->first_nested= tab;
4481
tab->on_expr_ref= &embedding->on_expr;
4482
tab->cond_equal= tbl->cond_equal;
4483
if (embedding->embedding)
4484
tab->first_upper= embedding->embedding->nested_join->first_nested;
4486
if (!tab->first_inner)
4487
tab->first_inner= nested_join->first_nested;
4488
if (++nested_join->counter_ < nested_join->join_list.elements)
4490
/* Table tab is the last inner table for nested join. */
4491
nested_join->first_nested->last_inner= tab;
4497
static bool make_join_select(JOIN *join,
4498
optimizer::SqlSelect *select,
4501
Session *session= join->session;
4502
optimizer::Position cur_pos;
4505
add_not_null_conds(join);
4506
table_map used_tables;
4507
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
4508
{ /* there may be a select without a cond. */
4509
if (join->tables > 1)
4510
cond->update_used_tables(); // Tablenr may have changed
4511
if (join->const_tables == join->tables &&
4512
session->lex->current_select->master_unit() ==
4513
&session->lex->unit) // not upper level SELECT
4514
join->const_table_map|=RAND_TABLE_BIT;
4515
{ // Check const tables
4517
make_cond_for_table(cond,
4518
join->const_table_map,
4520
for (JoinTable *tab= join->join_tab+join->const_tables;
4521
tab < join->join_tab+join->tables ; tab++)
4523
if (*tab->on_expr_ref)
4525
JoinTable *cond_tab= tab->first_inner;
4526
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
4527
join->const_table_map,
4531
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4534
tmp->quick_fix_field();
4535
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4536
new Item_cond_and(cond_tab->select_cond,
4538
if (! cond_tab->select_cond)
4540
cond_tab->select_cond->quick_fix_field();
4543
if (const_cond && ! const_cond->val_int())
4545
return 1; // Impossible const condition
4549
used_tables=((select->const_tables=join->const_table_map) |
4550
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4551
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4553
JoinTable *tab=join->join_tab+i;
4555
first_inner is the X in queries like:
4556
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
4558
JoinTable *first_inner_tab= tab->first_inner;
4559
table_map current_map= tab->table->map;
4560
bool use_quick_range=0;
4564
Following force including random expression in last table condition.
4565
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
4567
if (i == join->tables-1)
4568
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
4569
used_tables|=current_map;
4571
if (tab->type == AM_REF && tab->quick &&
4572
(uint32_t) tab->ref.key == tab->quick->index &&
4573
tab->ref.key_length < tab->quick->max_used_key_length)
4575
/* Range uses longer key; Use this instead of ref on key */
4580
tab->ref.key_parts= 0; // Don't use ref key.
4581
cur_pos= join->getPosFromOptimalPlan(i);
4582
cur_pos.setFanout(rows2double(tab->quick->records));
4584
We will use join cache here : prevent sorting of the first
4585
table only and sort at the end.
4587
if (i != join->const_tables && join->tables > join->const_tables + 1)
4593
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
4594
if (cond && !tmp && tab->quick)
4596
if (tab->type != AM_ALL)
4599
Don't use the quick method
4600
We come here in the case where we have 'key=constant' and
4601
the test is removed by make_cond_for_table()
4609
Hack to handle the case where we only refer to a table
4610
in the ON part of an OUTER JOIN. In this case we want the code
4611
below to check if we should use 'quick' instead.
4613
tmp= new Item_int((int64_t) 1,1); // Always true
4617
if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||
4618
tab->type == AM_EQ_REF)
4620
optimizer::SqlSelect *sel= tab->select= ((optimizer::SqlSelect*)
4621
session->memdup((unsigned char*) select,
4624
return 1; // End of memory
4626
If tab is an inner table of an outer join operation,
4627
add a match guard to the pushed down predicate.
4628
The guard will turn the predicate on only after
4629
the first match for outer tables is encountered.
4634
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
4635
a cond, so neutralize the hack above.
4637
if (! (tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
4639
tab->select_cond=sel->cond=tmp;
4642
tab->select_cond= sel->cond= NULL;
4644
sel->head=tab->table;
4647
/* Use quick key read if it's a constant and it's not used
4649
if (tab->needed_reg.none() && tab->type != AM_EQ_REF
4650
&& (tab->type != AM_REF || (uint32_t) tab->ref.key == tab->quick->index))
4652
sel->quick=tab->quick; // Use value from get_quick_...
4653
sel->quick_keys.reset();
4654
sel->needed_reg.reset();
4662
uint32_t ref_key= static_cast<uint32_t>(sel->head->reginfo.join_tab->ref.key + 1);
4663
if (i == join->const_tables && ref_key)
4665
if (tab->const_keys.any() &&
4666
tab->table->reginfo.impossible_range)
4669
else if (tab->type == AM_ALL && ! use_quick_range)
4671
if (tab->const_keys.any() &&
4672
tab->table->reginfo.impossible_range)
4673
return 1; // Impossible range
4675
We plan to scan all rows.
4676
Check again if we should use an index.
4677
We could have used an column from a previous table in
4678
the index if we are using limit and this is the first table
4681
cur_pos= join->getPosFromOptimalPlan(i);
4682
if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
4683
(! tab->const_keys.none() && (i == join->const_tables) &&
4684
(join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4686
/* Join with outer join condition */
4687
COND *orig_cond= sel->cond;
4688
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
4691
We can't call sel->cond->fix_fields,
4692
as it will break tab->on_expr if it's AND condition
4693
(fix_fields currently removes extra AND/OR levels).
4694
Yet attributes of the just built condition are not needed.
4695
Thus we call sel->cond->quick_fix_field for safety.
4697
if (sel->cond && ! sel->cond->fixed)
4698
sel->cond->quick_fix_field();
4700
if (sel->test_quick_select(session, tab->keys,
4701
used_tables & ~ current_map,
4702
(join->select_options &
4705
join->unit->select_limit_cnt), 0,
4709
Before reporting "Impossible WHERE" for the whole query
4710
we have to check isn't it only "impossible ON" instead
4712
sel->cond=orig_cond;
4713
if (! *tab->on_expr_ref ||
4714
sel->test_quick_select(session, tab->keys,
4715
used_tables & ~ current_map,
4716
(join->select_options &
4719
join->unit->select_limit_cnt),0,
4721
return 1; // Impossible WHERE
4724
sel->cond=orig_cond;
4726
/* Fix for EXPLAIN */
4729
cur_pos= join->getPosFromOptimalPlan(i);
4730
cur_pos.setFanout(static_cast<double>(sel->quick->records));
4735
sel->needed_reg= tab->needed_reg;
4736
sel->quick_keys.reset();
4738
if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
4739
!((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
4741
tab->keys= sel->quick_keys;
4742
tab->keys|= sel->needed_reg;
4743
tab->use_quick= (!sel->needed_reg.none() &&
4744
(select->quick_keys.none() ||
4746
(select->quick->records >= 100L)))) ?
4748
sel->read_tables= used_tables & ~current_map;
4750
if (i != join->const_tables && tab->use_quick != 2)
4751
{ /* Read with cache */
4753
(tmp=make_cond_for_table(cond,
4754
join->const_table_map |
4758
tab->cache.select= (optimizer::SqlSelect*)
4759
session->memdup((unsigned char*) sel, sizeof(optimizer::SqlSelect));
4760
tab->cache.select->cond= tmp;
4761
tab->cache.select->read_tables= join->const_table_map;
4768
Push down conditions from all on expressions.
4769
Each of these conditions are guarded by a variable
4770
that turns if off just before null complemented row for
4771
outer joins is formed. Thus, the condition from an
4772
'on expression' are guaranteed not to be checked for
4773
the null complemented row.
4776
/* First push down constant conditions from on expressions */
4777
for (JoinTable *join_tab= join->join_tab+join->const_tables;
4778
join_tab < join->join_tab+join->tables ; join_tab++)
4780
if (*join_tab->on_expr_ref)
4782
JoinTable *cond_tab= join_tab->first_inner;
4783
tmp= make_cond_for_table(*join_tab->on_expr_ref,
4784
join->const_table_map,
4788
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4791
tmp->quick_fix_field();
4792
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4793
new Item_cond_and(cond_tab->select_cond,tmp);
4794
if (! cond_tab->select_cond)
4796
cond_tab->select_cond->quick_fix_field();
4800
/* Push down non-constant conditions from on expressions */
4801
JoinTable *last_tab= tab;
4802
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
4805
Table tab is the last inner table of an outer join.
4806
An on expression is always attached to it.
4808
COND *on_expr= *first_inner_tab->on_expr_ref;
4810
table_map used_tables2= (join->const_table_map |
4811
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4812
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
4814
current_map= tab->table->map;
4815
used_tables2|= current_map;
4816
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
4820
JoinTable *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
4822
First add the guards for match variables of
4823
all embedding outer join operations.
4825
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
4830
Now add the guard turning the predicate off for
4831
the null complemented row.
4833
tmp_cond= new Item_func_trig_cond(tmp_cond,
4837
tmp_cond->quick_fix_field();
4838
/* Add the predicate to other pushed down predicates */
4839
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
4840
new Item_cond_and(cond_tab->select_cond,
4842
if (! cond_tab->select_cond)
4844
cond_tab->select_cond->quick_fix_field();
4847
first_inner_tab= first_inner_tab->first_upper;
4855
Plan refinement stage: do various set ups for the executioner
4858
make_join_readinfo()
4859
join Join being processed
4860
options Join's options (checking for SELECT_DESCRIBE,
4861
SELECT_NO_JOIN_CACHE)
4862
no_jbuf_after Don't use join buffering after table with this number.
4865
Plan refinement stage: do various set ups for the executioner
4866
- set up use of join buffering
4867
- push index conditions
4868
- increment counters
4873
true - Out of memory
4875
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
4878
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
4881
for (i=join->const_tables ; i < join->tables ; i++)
4883
JoinTable *tab=join->join_tab+i;
4884
Table *table=tab->table;
4885
bool using_join_cache;
4886
tab->read_record.table= table;
4887
tab->read_record.cursor= table->cursor;
4888
tab->next_select=sub_select; /* normal select */
4890
TODO: don't always instruct first table's ref/range access method to
4891
produce sorted output.
4893
tab->sorted= sorted;
4894
sorted= 0; // only first must be sorted
4895
if (tab->insideout_match_tab)
4897
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
4902
switch (tab->type) {
4903
case AM_SYSTEM: // Only happens with left join
4904
table->status=STATUS_NO_RECORD;
4905
tab->read_first_record= join_read_system;
4906
tab->read_record.read_record= join_no_more_records;
4908
case AM_CONST: // Only happens with left join
4909
table->status=STATUS_NO_RECORD;
4910
tab->read_first_record= join_read_const;
4911
tab->read_record.read_record= join_no_more_records;
4912
if (table->covering_keys.test(tab->ref.key) &&
4916
table->cursor->extra(HA_EXTRA_KEYREAD);
4920
table->status=STATUS_NO_RECORD;
4923
delete tab->select->quick;
4924
tab->select->quick=0;
4928
tab->read_first_record= join_read_key;
4929
tab->read_record.read_record= join_no_more_records;
4930
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4933
table->cursor->extra(HA_EXTRA_KEYREAD);
4936
case AM_REF_OR_NULL:
4938
table->status=STATUS_NO_RECORD;
4941
delete tab->select->quick;
4942
tab->select->quick=0;
4946
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4949
table->cursor->extra(HA_EXTRA_KEYREAD);
4951
if (tab->type == AM_REF)
4953
tab->read_first_record= join_read_always_key;
4954
tab->read_record.read_record= tab->insideout_match_tab?
4955
join_read_next_same_diff : join_read_next_same;
4959
tab->read_first_record= join_read_always_key_or_null;
4960
tab->read_record.read_record= join_read_next_same_or_null;
4965
If previous table use cache
4966
If the incoming data set is already sorted don't use cache.
4968
table->status=STATUS_NO_RECORD;
4969
using_join_cache= false;
4970
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
4971
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
4972
!tab->insideout_match_tab)
4974
if ((options & SELECT_DESCRIBE) ||
4975
!join_init_cache(join->session,join->join_tab+join->const_tables,
4976
i-join->const_tables))
4978
using_join_cache= true;
4979
tab[-1].next_select=sub_select_cache; /* Patch previous */
4982
/* These init changes read_record */
4983
if (tab->use_quick == 2)
4985
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
4986
tab->read_first_record= join_init_quick_read_record;
4988
status_var_increment(join->session->status_var.select_range_check_count);
4992
tab->read_first_record= join_init_read_record;
4993
if (i == join->const_tables)
4995
if (tab->select && tab->select->quick)
4998
status_var_increment(join->session->status_var.select_range_count);
5002
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
5004
status_var_increment(join->session->status_var.select_scan_count);
5009
if (tab->select && tab->select->quick)
5012
status_var_increment(join->session->status_var.select_full_range_join_count);
5016
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
5018
status_var_increment(join->session->status_var.select_full_join_count);
5021
if (!table->no_keyread)
5023
if (tab->select && tab->select->quick &&
5024
tab->select->quick->index != MAX_KEY && //not index_merge
5025
table->covering_keys.test(tab->select->quick->index))
5028
table->cursor->extra(HA_EXTRA_KEYREAD);
5030
else if (!table->covering_keys.none() &&
5031
!(tab->select && tab->select->quick))
5032
{ // Only read index tree
5033
if (!tab->insideout_match_tab)
5036
See bug #26447: "Using the clustered index for a table scan
5037
is always faster than using a secondary index".
5039
if (table->s->primary_key != MAX_KEY &&
5040
table->cursor->primary_key_is_clustered())
5041
tab->index= table->s->primary_key;
5043
tab->index= table->find_shortest_key(&table->covering_keys);
5045
tab->read_first_record= join_read_first;
5046
tab->type= AM_NEXT; // Read with index_first / index_next
5058
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
5062
/** Update the dependency map for the tables. */
5063
static void update_depend_map(JOIN *join)
5065
JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
5067
for (; join_tab != end ; join_tab++)
5069
table_reference_st *ref= &join_tab->ref;
5070
table_map depend_map= 0;
5071
Item **item=ref->items;
5073
for (i=0 ; i < ref->key_parts ; i++,item++)
5074
depend_map|=(*item)->used_tables();
5075
ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;
5076
depend_map&= ~OUTER_REF_TABLE_BIT;
5077
for (JoinTable **tab=join->map2table; depend_map; tab++,depend_map>>=1 )
5080
ref->depend_map|=(*tab)->ref.depend_map;
5085
/** Update the dependency map for the sort order. */
5086
static void update_depend_map(JOIN *join, order_st *order)
5088
for (; order ; order=order->next)
5090
table_map depend_map;
5091
order->item[0]->update_used_tables();
5092
order->depend_map=depend_map=order->item[0]->used_tables();
5093
// Not item_sum(), RAND() and no reference to table outside of sub select
5094
if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))
5095
&& !order->item[0]->with_sum_func)
5097
for (JoinTable **tab=join->map2table; depend_map; tab++, depend_map>>=1)
5100
order->depend_map|=(*tab)->ref.depend_map;
5107
Remove all constants and check if order_st only contains simple
5110
simple_order is set to 1 if sort_order only uses fields from head table
5111
and the head table is not a LEFT JOIN table.
5113
@param join Join handler
5114
@param first_order List of SORT or GROUP order
5115
@param cond WHERE statement
5116
@param change_list Set to 1 if we should remove things from list.
5117
If this is not set, then only simple_order is
5119
@param simple_order Set to 1 if we are only using simple expressions
5122
Returns new sort order
5124
static order_st *remove_constants(JOIN *join,order_st *first_order, COND *cond, bool change_list, bool *simple_order)
5126
if (join->tables == join->const_tables)
5127
return change_list ? 0 : first_order; // No need to sort
5129
order_st *order,**prev_ptr;
5130
table_map first_table= join->join_tab[join->const_tables].table->map;
5131
table_map not_const_tables= ~join->const_table_map;
5134
prev_ptr= &first_order;
5135
*simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;
5137
/* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
5139
update_depend_map(join, first_order);
5140
for (order=first_order; order ; order=order->next)
5142
table_map order_tables=order->item[0]->used_tables();
5143
if (order->item[0]->with_sum_func)
5144
*simple_order=0; // Must do a temp table to sort
5145
else if (!(order_tables & not_const_tables))
5147
if (order->item[0]->with_subselect)
5148
order->item[0]->val_str(&order->item[0]->str_value);
5149
continue; // skip const item
5153
if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))
5158
if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
5162
if ((ref=order_tables & (not_const_tables ^ first_table)))
5164
if (!(order_tables & first_table) &&
5165
only_eq_ref_tables(join,first_order, ref))
5169
*simple_order=0; // Must do a temp table to sort
5174
*prev_ptr= order; // use this entry
5175
prev_ptr= &order->next;
5179
if (prev_ptr == &first_order) // Nothing to sort/group
5181
return(first_order);
5184
static int return_zero_rows(JOIN *join,
5185
select_result *result,
5189
uint64_t select_options,
5193
if (select_options & SELECT_DESCRIBE)
5195
optimizer::ExplainPlan planner(join,
5200
planner.printPlan();
5208
for (TableList *table= tables; table; table= table->next_leaf)
5209
table->table->mark_as_null_row(); // All fields are NULL
5210
if (having && having->val_int() == 0)
5213
if (! (result->send_fields(fields)))
5217
List_iterator_fast<Item> it(fields);
5219
while ((item= it++))
5220
item->no_rows_in_result();
5221
result->send_data(fields);
5223
result->send_eof(); // Should be safe
5225
/* Update results for FOUND_ROWS */
5226
join->session->limit_found_rows= join->session->examined_row_count= 0;
5231
Simplify joins replacing outer joins by inner joins whenever it's
5234
The function, during a retrieval of join_list, eliminates those
5235
outer joins that can be converted into inner join, possibly nested.
5236
It also moves the on expressions for the converted outer joins
5237
and from inner joins to conds.
5238
The function also calculates some attributes for nested joins:
5242
- on_expr_dep_tables
5243
The first two attributes are used to test whether an outer join can
5244
be substituted for an inner join. The third attribute represents the
5245
relation 'to be dependent on' for tables. If table t2 is dependent
5246
on table t1, then in any evaluated execution plan table access to
5247
table t2 must precede access to table t2. This relation is used also
5248
to check whether the query contains invalid cross-references.
5249
The forth attribute is an auxiliary one and is used to calculate
5251
As the attribute dep_tables qualifies possibles orders of tables in the
5252
execution plan, the dependencies required by the straight join
5253
modifiers are reflected in this attribute as well.
5254
The function also removes all braces that can be removed from the join
5255
expression without changing its meaning.
5258
An outer join can be replaced by an inner join if the where condition
5259
or the on expression for an embedding nested join contains a conjunctive
5260
predicate rejecting null values for some attribute of the inner tables.
5264
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5266
the predicate t2.b < 5 rejects nulls.
5267
The query is converted first to:
5269
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5271
then to the equivalent form:
5273
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
5277
Similarly the following query:
5279
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
5284
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
5288
One conversion might trigger another:
5290
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
5291
LEFT JOIN t3 ON t3.b=t2.b
5292
WHERE t3 IS NOT NULL =>
5293
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
5294
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
5295
SELECT * FROM t1, t2, t3
5296
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
5299
The function removes all unnecessary braces from the expression
5300
produced by the conversions.
5303
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5305
finally is converted to:
5307
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5312
It also will remove braces from the following queries:
5314
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
5315
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
5318
The benefit of this simplification procedure is that it might return
5319
a query for which the optimizer can evaluate execution plan with more
5320
join orders. With a left join operation the optimizer does not
5321
consider any plan where one of the inner tables is before some of outer
5325
The function is implemented by a recursive procedure. On the recursive
5326
ascent all attributes are calculated, all outer joins that can be
5327
converted are replaced and then all unnecessary braces are removed.
5328
As join list contains join tables in the reverse order sequential
5329
elimination of outer joins does not require extra recursive calls.
5332
Remove all semi-joins that have are within another semi-join (i.e. have
5333
an "ancestor" semi-join nest)
5336
Here is an example of a join query with invalid cross references:
5338
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
5341
@param join reference to the query info
5342
@param join_list list representation of the join to be converted
5343
@param conds conditions to add on expressions for converted joins
5344
@param top true <=> conds is the where condition
5347
- The new condition, if success
5350
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top)
5353
nested_join_st *nested_join;
5354
TableList *prev_table= 0;
5355
List_iterator<TableList> li(*join_list);
5358
Try to simplify join operations from join_list.
5359
The most outer join operation is checked for conversion first.
5361
while ((table= li++))
5363
table_map used_tables;
5364
table_map not_null_tables= (table_map) 0;
5366
if ((nested_join= table->nested_join))
5369
If the element of join_list is a nested join apply
5370
the procedure to its nested join list first.
5374
Item *expr= table->on_expr;
5376
If an on expression E is attached to the table,
5377
check all null rejected predicates in this expression.
5378
If such a predicate over an attribute belonging to
5379
an inner table of an embedded outer join is found,
5380
the outer join is converted to an inner join and
5381
the corresponding on expression is added to E.
5383
expr= simplify_joins(join, &nested_join->join_list, expr, false);
5385
if (!table->prep_on_expr || expr != table->on_expr)
5389
table->on_expr= expr;
5390
table->prep_on_expr= expr->copy_andor_structure(join->session);
5393
nested_join->used_tables= (table_map) 0;
5394
nested_join->not_null_tables=(table_map) 0;
5395
conds= simplify_joins(join, &nested_join->join_list, conds, top);
5396
used_tables= nested_join->used_tables;
5397
not_null_tables= nested_join->not_null_tables;
5401
if (!table->prep_on_expr)
5402
table->prep_on_expr= table->on_expr;
5403
used_tables= table->table->map;
5405
not_null_tables= conds->not_null_tables();
5408
if (table->embedding)
5410
table->embedding->nested_join->used_tables|= used_tables;
5411
table->embedding->nested_join->not_null_tables|= not_null_tables;
5414
if (!table->outer_join || (used_tables & not_null_tables))
5417
For some of the inner tables there are conjunctive predicates
5418
that reject nulls => the outer join can be replaced by an inner join.
5420
table->outer_join= 0;
5423
/* Add ON expression to the WHERE or upper-level ON condition. */
5426
conds= and_conds(conds, table->on_expr);
5427
conds->top_level_item();
5428
/* conds is always a new item as both cond and on_expr existed */
5429
assert(!conds->fixed);
5430
conds->fix_fields(join->session, &conds);
5433
conds= table->on_expr;
5434
table->prep_on_expr= table->on_expr= 0;
5442
Only inner tables of non-convertible outer joins
5443
remain with on_expr.
5447
table->dep_tables|= table->on_expr->used_tables();
5448
if (table->embedding)
5450
table->dep_tables&= ~table->embedding->nested_join->used_tables;
5452
Embedding table depends on tables used
5453
in embedded on expressions.
5455
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
5458
table->dep_tables&= ~table->table->map;
5463
/* The order of tables is reverse: prev_table follows table */
5464
if (prev_table->straight)
5465
prev_table->dep_tables|= used_tables;
5466
if (prev_table->on_expr)
5468
prev_table->dep_tables|= table->on_expr_dep_tables;
5469
table_map prev_used_tables= prev_table->nested_join ?
5470
prev_table->nested_join->used_tables :
5471
prev_table->table->map;
5473
If on expression contains only references to inner tables
5474
we still make the inner tables dependent on the outer tables.
5475
It would be enough to set dependency only on one outer table
5476
for them. Yet this is really a rare case.
5478
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5479
prev_table->dep_tables|= used_tables;
5486
Flatten nested joins that can be flattened.
5487
no ON expression and not a semi-join => can be flattened.
5490
while ((table= li++))
5492
nested_join= table->nested_join;
5493
if (nested_join && !table->on_expr)
5496
List_iterator<TableList> it(nested_join->join_list);
5499
tbl->embedding= table->embedding;
5500
tbl->join_list= table->join_list;
5502
li.replace(nested_join->join_list);
5508
static int remove_duplicates(JOIN *join, Table *entry,List<Item> &fields, Item *having)
5511
uint32_t reclength,offset;
5512
uint32_t field_count;
5513
Session *session= join->session;
5515
entry->reginfo.lock_type=TL_WRITE;
5517
/* Calculate how many saved fields there is in list */
5519
List_iterator<Item> it(fields);
5523
if (item->get_tmp_table_field() && ! item->const_item())
5527
if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)
5528
{ // only const items with no OPTION_FOUND_ROWS
5529
join->unit->select_limit_cnt= 1; // Only send first row
5532
Field **first_field=entry->field+entry->s->fields - field_count;
5533
offset= (field_count ?
5534
entry->field[entry->s->fields - field_count]->
5535
offset(entry->record[0]) : 0);
5536
reclength= entry->s->reclength-offset;
5538
entry->free_io_cache(); // Safety
5539
entry->cursor->info(HA_STATUS_VARIABLE);
5540
if (entry->s->db_type() == heap_engine ||
5541
(!entry->s->blob_fields &&
5542
((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->cursor->stats.records <
5543
session->variables.sortbuff_size)))
5544
error= remove_dup_with_hash_index(join->session, entry,
5545
field_count, first_field,
5548
error= remove_dup_with_compare(join->session, entry, first_field, offset,
5551
free_blobs(first_field);
5556
Function to setup clauses without sum functions.
5558
static int setup_without_group(Session *session,
5559
Item **ref_pointer_array,
5563
List<Item> &all_fields,
5567
bool *hidden_group_fields)
5570
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
5572
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5573
res= session->setup_conds(tables, conds);
5575
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
5576
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
5578
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5579
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
5580
group, hidden_group_fields);
5581
session->lex->allow_sum_func= save_allow_sum_func;
5586
Calculate the best possible join and initialize the join structure.
5593
static bool make_join_statistics(JOIN *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5598
uint32_t table_count;
5599
uint32_t const_count;
5601
table_map found_const_table_map;
5602
table_map all_table_map;
5603
table_map found_ref;
5607
Table **table_vector= NULL;
5608
JoinTable *stat= NULL;
5609
JoinTable *stat_end= NULL;
5611
JoinTable **stat_ref= NULL;
5612
optimizer::KeyUse *keyuse= NULL;
5613
optimizer::KeyUse *start_keyuse= NULL;
5614
table_map outer_join= 0;
5615
vector<optimizer::SargableParam> sargables;
5616
JoinTable *stat_vector[MAX_TABLES+1];
5617
optimizer::Position *partial_pos;
5619
table_count= join->tables;
5620
stat= (JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
5621
stat_ref= (JoinTable**) join->session->alloc(sizeof(JoinTable*)*MAX_TABLES);
5622
table_vector= (Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
5623
if (! stat || ! stat_ref || ! table_vector)
5626
join->best_ref=stat_vector;
5628
stat_end=stat+table_count;
5629
found_const_table_map= all_table_map=0;
5634
s++, tables= tables->next_leaf, i++)
5636
TableList *embedding= tables->embedding;
5639
s->const_keys.reset();
5640
s->checked_keys.reset();
5641
s->needed_reg.reset();
5642
table_vector[i]=s->table=table=tables->table;
5643
table->pos_in_table_list= tables;
5644
error= table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5647
table->print_error(error, MYF(0));
5650
table->quick_keys.reset();
5651
table->reginfo.join_tab=s;
5652
table->reginfo.not_exists_optimize=0;
5653
memset(table->const_key_parts, 0,
5654
sizeof(key_part_map)*table->s->keys);
5655
all_table_map|= table->map;
5657
s->info=0; // For describe
5659
s->dependent= tables->dep_tables;
5660
s->key_dependent= 0;
5661
table->quick_condition_rows= table->cursor->stats.records;
5663
s->on_expr_ref= &tables->on_expr;
5664
if (*s->on_expr_ref)
5666
/* s is the only inner table of an outer join */
5667
if (!table->cursor->stats.records && !embedding)
5669
s->dependent= 0; // Ignore LEFT JOIN depend.
5670
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5673
outer_join|= table->map;
5674
s->embedding_map.reset();
5675
for (;embedding; embedding= embedding->embedding)
5676
s->embedding_map|= embedding->nested_join->nj_map;
5679
if (embedding && !(false && ! embedding->embedding))
5681
/* s belongs to a nested join, maybe to several embedded joins */
5682
s->embedding_map.reset();
5685
nested_join_st *nested_join= embedding->nested_join;
5686
s->embedding_map|= nested_join->nj_map;
5687
s->dependent|= embedding->dep_tables;
5688
embedding= embedding->embedding;
5689
outer_join|= nested_join->used_tables;
5694
if ((table->cursor->stats.records <= 1) && !s->dependent &&
5695
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5696
!join->no_const_tables)
5698
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5702
join->outer_join=outer_join;
5704
if (join->outer_join)
5707
Build transitive closure for relation 'to be dependent on'.
5708
This will speed up the plan search for many cases with outer joins,
5709
as well as allow us to catch illegal cross references/
5710
Warshall's algorithm is used to build the transitive closure.
5711
As we use bitmaps to represent the relation the complexity
5712
of the algorithm is O((number of tables)^2).
5714
for (i= 0, s= stat ; i < table_count ; i++, s++)
5716
for (uint32_t j= 0 ; j < table_count ; j++)
5718
table= stat[j].table;
5719
if (s->dependent & table->map)
5720
s->dependent |= table->reginfo.join_tab->dependent;
5723
s->table->maybe_null= 1;
5725
/* Catch illegal cross references for outer joins */
5726
for (i= 0, s= stat ; i < table_count ; i++, s++)
5728
if (s->dependent & s->table->map)
5730
join->tables=0; // Don't use join->table
5731
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
5734
s->key_dependent= s->dependent;
5738
if (conds || outer_join)
5739
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
5740
conds, join->cond_equal,
5741
~outer_join, join->select_lex, sargables))
5744
/* Read tables with 0 or 1 rows (system tables) */
5745
join->const_table_map= 0;
5747
optimizer::Position *p_pos= join->getFirstPosInPartialPlan();
5748
optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5749
while (p_pos < p_end)
5752
s= p_pos->getJoinTable();
5754
join->const_table_map|=s->table->map;
5755
if ((tmp= join_read_const_table(s, p_pos)))
5758
return 1; // Fatal error
5761
found_const_table_map|= s->table->map;
5765
/* loop until no more const tables are found */
5769
more_const_tables_found:
5774
We only have to loop from stat_vector + const_count as
5775
set_position() will move all const_tables first in stat_vector
5778
for (JoinTable **pos= stat_vector+const_count; (s= *pos); pos++)
5783
If equi-join condition by a key is null rejecting and after a
5784
substitution of a const table the key value happens to be null
5785
then we can state that there are no matches for this equi-join.
5787
if ((keyuse= s->keyuse) && *s->on_expr_ref && s->embedding_map.none())
5790
When performing an outer join operation if there are no matching rows
5791
for the single row of the outer table all the inner tables are to be
5792
null complemented and thus considered as constant tables.
5793
Here we apply this consideration to the case of outer join operations
5794
with a single inner table only because the case with nested tables
5795
would require a more thorough analysis.
5796
TODO. Apply single row substitution to null complemented inner tables
5797
for nested outer join operations.
5799
while (keyuse->getTable() == table)
5801
if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&
5802
keyuse->getVal()->is_null() && keyuse->isNullRejected())
5805
table->mark_as_null_row();
5806
found_const_table_map|= table->map;
5807
join->const_table_map|= table->map;
5808
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5809
goto more_const_tables_found;
5815
if (s->dependent) // If dependent on some table
5817
// All dep. must be constants
5818
if (s->dependent & ~(found_const_table_map))
5820
if (table->cursor->stats.records <= 1L &&
5821
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5822
!table->pos_in_table_list->embedding)
5826
join->const_table_map|=table->map;
5827
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5828
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5829
if ((tmp= join_read_const_table(s, partial_pos)))
5832
return 1; // Fatal error
5835
found_const_table_map|= table->map;
5839
/* check if table can be read by key or table only uses const refs */
5840
if ((keyuse=s->keyuse))
5843
while (keyuse->getTable() == table)
5845
start_keyuse= keyuse;
5846
key= keyuse->getKey();
5847
s->keys.set(key); // QQ: remove this ?
5854
if (keyuse->getVal()->type() != Item::NULL_ITEM &&
5855
! keyuse->getOptimizeFlags())
5857
if (! ((~found_const_table_map) & keyuse->getUsedTables()))
5858
const_ref.set(keyuse->getKeypart());
5860
refs|= keyuse->getUsedTables();
5861
eq_part.set(keyuse->getKeypart());
5864
} while (keyuse->getTable() == table && keyuse->getKey() == key);
5866
if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
5867
! table->pos_in_table_list->embedding)
5869
if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
5871
if (const_ref == eq_part)
5872
{ // Found everything for ref.
5876
join->const_table_map|= table->map;
5877
set_position(join, const_count++, s, start_keyuse);
5878
if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
5880
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5881
if ((tmp=join_read_const_table(s, partial_pos)))
5884
return 1; // Fatal error
5887
found_const_table_map|= table->map;
5891
found_ref|= refs; // Table is const if all refs are const
5893
else if (const_ref == eq_part)
5894
s->const_keys.set(key);
5899
} while (join->const_table_map & found_ref && ref_changed);
5902
Update info on indexes that can be used for search lookups as
5903
reading const tables may has added new sargable predicates.
5905
if (const_count && ! sargables.empty())
5907
vector<optimizer::SargableParam>::iterator iter= sargables.begin();
5908
while (iter != sargables.end())
5910
Field *field= (*iter).getField();
5911
JoinTable *join_tab= field->table->reginfo.join_tab;
5912
key_map possible_keys= field->key_start;
5913
possible_keys&= field->table->keys_in_use_for_query;
5914
bool is_const= true;
5915
for (uint32_t j= 0; j < (*iter).getNumValues(); j++)
5916
is_const&= (*iter).isConstItem(j);
5918
join_tab[0].const_keys|= possible_keys;
5923
/* Calc how many (possible) matched records in each table */
5925
for (s=stat ; s < stat_end ; s++)
5927
if (s->type == AM_SYSTEM || s->type == AM_CONST)
5929
/* Only one matching row */
5930
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
5933
/* Approximate found rows and time to read them */
5934
s->found_records=s->records=s->table->cursor->stats.records;
5935
s->read_time=(ha_rows) s->table->cursor->scan_time();
5938
Set a max range of how many seeks we can expect when using keys
5939
This is can't be to high as otherwise we are likely to use
5942
s->worst_seeks= min((double) s->found_records / 10,
5943
(double) s->read_time*3);
5944
if (s->worst_seeks < 2.0) // Fix for small tables
5948
Add to stat->const_keys those indexes for which all group fields or
5949
all select distinct fields participate in one index.
5951
add_group_and_distinct_keys(join, s);
5953
if (s->const_keys.any() &&
5954
!s->table->pos_in_table_list->embedding)
5957
optimizer::SqlSelect *select= NULL;
5958
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);
5961
records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
5962
s->quick=select->quick;
5963
s->needed_reg=select->needed_reg;
5965
if (records == 0 && s->table->reginfo.impossible_range)
5968
Impossible WHERE or ON expression
5969
In case of ON, we mark that the we match one empty NULL row.
5970
In case of WHERE, don't set found_const_table_map to get the
5971
caller to abort with a zero row result.
5973
join->const_table_map|= s->table->map;
5974
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5976
if (*s->on_expr_ref)
5978
/* Generate empty row */
5979
s->info= "Impossible ON condition";
5980
found_const_table_map|= s->table->map;
5982
s->table->mark_as_null_row(); // All fields are NULL
5985
if (records != HA_POS_ERROR)
5987
s->found_records=records;
5988
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
5994
join->join_tab=stat;
5995
join->map2table=stat_ref;
5996
join->table= join->all_tables=table_vector;
5997
join->const_tables=const_count;
5998
join->found_const_table_map=found_const_table_map;
6000
/* Find an optimal join order of the non-constant tables. */
6001
if (join->const_tables != join->tables)
6003
optimize_keyuse(join, keyuse_array);
6004
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->query.c_str(), join->session->thread_id);
6005
bool res= choose_plan(join, all_table_map & ~join->const_table_map);
6006
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);
6012
join->copyPartialPlanIntoOptimalPlan(join->const_tables);
6013
join->best_read= 1.0;
6015
/* Generate an execution plan from the found optimal join order. */
6016
return (join->session->killed || get_best_combination(join));
6020
Assign each nested join structure a bit in the nested join bitset.
6022
Assign each nested join structure (except "confluent" ones - those that
6023
embed only one element) a bit in the nested join bitset.
6025
@param join Join being processed
6026
@param join_list List of tables
6027
@param first_unused Number of first unused bit in the nest joing bitset before the
6031
This function is called after simplify_joins(), when there are no
6032
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
6033
we will not run out of bits in the nested join bitset.
6036
First unused bit in the nest join bitset after the call.
6038
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
6040
List_iterator<TableList> li(*join_list);
6042
while ((table= li++))
6044
nested_join_st *nested_join;
6045
if ((nested_join= table->nested_join))
6048
It is guaranteed by simplify_joins() function that a nested join
6049
that has only one child is either
6050
- a single-table view (the child is the underlying table), or
6051
- a single-table semi-join nest
6053
We don't assign bits to such sj-nests because
6054
1. it is redundant (a "sequence" of one table cannot be interleaved
6056
2. we could run out of bits in the nested join bitset otherwise.
6058
if (nested_join->join_list.elements != 1)
6060
/* Don't assign bits to sj-nests */
6062
nested_join->nj_map.set(first_unused++);
6063
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
6068
return(first_unused);
6073
Return table number if there is only one table in sort order
6074
and group and order is compatible, else return 0.
6076
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables)
6078
table_map map= (table_map) 0;
6081
a= b; // Only one need to be given
6085
for (; a && b; a=a->next,b=b->next)
6087
if (!(*a->item)->eq(*b->item,1))
6088
return (Table *) NULL;
6089
map|= a->item[0]->used_tables();
6091
if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
6092
return (Table *) NULL;
6094
for (; !(map & tables->table->map); tables= tables->next_leaf) {};
6095
if (map != tables->table->map)
6096
return (Table *) NULL; // More than one table
6097
return tables->table;
6101
Set nested_join_st::counter=0 in all nested joins in passed list.
6103
Recursively set nested_join_st::counter=0 for all nested joins contained in
6104
the passed join_list.
6106
@param join_list List of nested joins to process. It may also contain base
6107
tables which will be ignored.
6109
static void reset_nj_counters(List<TableList> *join_list)
6111
List_iterator<TableList> li(*join_list);
6113
while ((table= li++))
6115
nested_join_st *nested_join;
6116
if ((nested_join= table->nested_join))
6118
nested_join->counter_= 0;
6119
reset_nj_counters(&nested_join->join_list);
6126
Return 1 if second is a subpart of first argument.
6128
If first parts has different direction, change it to second part
6129
(group is sorted like order)
6131
static bool test_if_subpart(order_st *a,order_st *b)
6133
for (; a && b; a=a->next,b=b->next)
6135
if ((*a->item)->eq(*b->item,1))
6144
Nested joins perspective: Remove the last table from the join order.
6146
Remove the last table from the partial join order and update the nested
6147
joins counters and join->cur_embedding_map. It is ok to call this
6148
function for the first table in join order (for which
6149
check_interleaving_with_nj has not been called)
6151
@param last join table to remove, it is assumed to be the last in current
6154
static void restore_prev_nj_state(JoinTable *last)
6156
TableList *last_emb= last->table->pos_in_table_list->embedding;
6157
JOIN *join= last->join;
6160
if (last_emb->on_expr)
6162
if (!(--last_emb->nested_join->counter_))
6163
join->cur_embedding_map&= ~last_emb->nested_join->nj_map;
6164
else if (last_emb->nested_join->join_list.elements-1 ==
6165
last_emb->nested_join->counter_)
6166
join->cur_embedding_map|= last_emb->nested_join->nj_map;
6170
last_emb= last_emb->embedding;
6175
Determine if the set is already ordered for order_st BY, so it can
6176
disable join cache because it will change the ordering of the results.
6177
Code handles sort table that is at any location (not only first after
6178
the const tables) despite the fact that it's currently prohibited.
6179
We must disable join cache if the first non-const table alone is
6180
ordered. If there is a temp table the ordering is done as a last
6181
operation and doesn't prevent join cache usage.
6183
static uint32_t make_join_orderinfo(JOIN *join)
6187
return join->tables;
6189
for (i=join->const_tables ; i < join->tables ; i++)
6191
JoinTable *tab= join->join_tab+i;
6192
Table *table= tab->table;
6193
if ((table == join->sort_by_table &&
6194
(!join->order || join->skip_sort_order)) ||
6195
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
6204
Create a condition for a const reference and add this to the
6205
currenct select for the table.
6207
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)
6209
if (!join_tab->ref.key_parts)
6212
Item_cond_and *cond=new Item_cond_and();
6213
Table *table=join_tab->table;
6218
for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6220
Field *field=table->field[table->key_info[join_tab->ref.key].key_part[i].
6222
Item *value=join_tab->ref.items[i];
6223
cond->add(new Item_func_equal(new Item_field(field), value));
6225
if (session->is_fatal_error)
6229
cond->fix_fields(session, (Item**)&cond);
6230
if (join_tab->select)
6232
error=(int) cond->add(join_tab->select->cond);
6233
join_tab->select_cond=join_tab->select->cond=cond;
6235
else if ((join_tab->select= optimizer::make_select(join_tab->table, 0, 0, cond, 0,
6237
join_tab->select_cond=cond;
6239
return(error ? true : false);
6242
static void free_blobs(Field **ptr)
6244
for (; *ptr ; ptr++)
6246
if ((*ptr)->flags & BLOB_FLAG)
6247
((Field_blob *) (*ptr))->free();
6252
@} (end of group Query_Optimizer)
6255
} /* namespace drizzled */
added
removed
drizzled/join.cc
