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/optimizer/access_method_factory.h"
55
#include "drizzled/optimizer/access_method.h"
56
#include "drizzled/records.h"
57
#include "drizzled/probes.h"
58
#include "drizzled/internal/my_bit.h"
59
#include "drizzled/internal/my_sys.h"
60
#include "drizzled/internal/iocache.h"
69
extern plugin::StorageEngine *heap_engine;
70
extern std::bitset<12> test_flags;
72
/** Declarations of static functions used in this source file. */
73
static bool make_group_fields(Join *main_join, Join *curr_join);
74
static void calc_group_buffer(Join *join,order_st *group);
75
static bool alloc_group_fields(Join *join,order_st *group);
76
static uint32_t cache_record_length(Join *join, uint32_t index);
77
static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref);
78
static bool get_best_combination(Join *join);
79
static void set_position(Join *join,
82
optimizer::KeyUse *key);
83
static bool choose_plan(Join *join,table_map join_tables);
84
static void best_access_path(Join *join, JoinTable *s,
86
table_map remaining_tables,
90
static void optimize_straight_join(Join *join, table_map join_tables);
91
static bool greedy_search(Join *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
92
static bool best_extension_by_limited_search(Join *join,
93
table_map remaining_tables,
98
uint32_t prune_level);
99
static uint32_t determine_search_depth(Join* join);
100
static bool make_simple_join(Join *join,Table *tmp_table);
101
static void make_outerjoin_info(Join *join);
102
static bool make_join_select(Join *join, optimizer::SqlSelect *select,COND *item);
103
static bool make_join_readinfo(Join *join);
104
static void update_depend_map(Join *join);
105
static void update_depend_map(Join *join, order_st *order);
106
static order_st *remove_constants(Join *join,order_st *first_order,COND *cond, bool change_list, bool *simple_order);
107
static int return_zero_rows(Join *join,
112
uint64_t select_options,
115
static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top);
116
static int remove_duplicates(Join *join,Table *entry,List<Item> &fields, Item *having);
117
static int setup_without_group(Session *session,
118
Item **ref_pointer_array,
122
List<Item> &all_fields,
126
bool *hidden_group_fields);
127
static bool make_join_statistics(Join *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
128
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
129
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
130
static void reset_nj_counters(List<TableList> *join_list);
131
static bool test_if_subpart(order_st *a,order_st *b);
132
static void restore_prev_nj_state(JoinTable *last);
133
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
134
static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
137
Prepare of whole select (including sub queries in future).
140
Add check of calculation of GROUP functions and fields:
141
SELECT COUNT(*)+table.col1 from table1;
148
int Join::prepare(Item ***rref_pointer_array,
149
TableList *tables_init,
153
order_st *order_init,
154
order_st *group_init,
156
Select_Lex *select_lex_arg,
157
Select_Lex_Unit *unit_arg)
159
// to prevent double initialization on EXPLAIN
165
group_list= group_init;
167
tables_list= tables_init;
168
select_lex= select_lex_arg;
169
select_lex->join= this;
170
join_list= &select_lex->top_join_list;
171
union_part= unit_arg->is_union();
173
session->lex->current_select->is_item_list_lookup= 1;
175
If we have already executed SELECT, then it have not sense to prevent
176
its table from update (see unique_table())
178
if (session->derived_tables_processing)
179
select_lex->exclude_from_table_unique_test= true;
181
/* Check that all tables, fields, conds and order are ok */
183
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
184
setup_tables_and_check_access(session, &select_lex->context, join_list,
185
tables_list, &select_lex->leaf_tables,
191
TableList *table_ptr;
192
for (table_ptr= select_lex->leaf_tables;
194
table_ptr= table_ptr->next_leaf)
197
if (setup_wild(session, fields_list, &all_fields, wild_num) ||
198
select_lex->setup_ref_array(session, og_num) ||
199
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
201
setup_without_group(session, (*rref_pointer_array), tables_list,
202
select_lex->leaf_tables, fields_list,
203
all_fields, &conds, order, group_list,
204
&hidden_group_fields))
207
ref_pointer_array= *rref_pointer_array;
211
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
212
session->where="having clause";
213
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
214
select_lex->having_fix_field= 1;
215
bool having_fix_rc= (!having->fixed &&
216
(having->fix_fields(session, &having) ||
217
having->check_cols(1)));
218
select_lex->having_fix_field= 0;
219
if (having_fix_rc || session->is_error())
221
session->lex->allow_sum_func= save_allow_sum_func;
225
Item_subselect *subselect;
226
Item_in_subselect *in_subs= NULL;
228
Are we in a subquery predicate?
229
TODO: the block below will be executed for every PS execution without need.
231
if ((subselect= select_lex->master_unit()->item))
233
if (subselect->substype() == Item_subselect::IN_SUBS)
234
in_subs= (Item_in_subselect*)subselect;
237
bool do_materialize= true;
239
Check if the subquery predicate can be executed via materialization.
240
The required conditions are:
241
1. Subquery predicate is an IN/=ANY subq predicate
242
2. Subquery is a single SELECT (not a UNION)
243
3. Subquery is not a table-less query. In this case there is no
244
point in materializing.
245
4. Subquery predicate is a top-level predicate
246
(this implies it is not negated)
247
TODO: this is a limitation that should be lifeted once we
248
implement correct NULL semantics (WL#3830)
249
5. Subquery is non-correlated
251
This is an overly restrictive condition. It can be extended to:
252
(Subquery is non-correlated ||
253
Subquery is correlated to any query outer to IN predicate ||
254
(Subquery is correlated to the immediate outer query &&
255
Subquery !contains {GROUP BY, ORDER BY [LIMIT],
256
aggregate functions) && subquery predicate is not under "NOT IN"))
257
6. No execution method was already chosen (by a prepared statement).
259
(*) The subquery must be part of a SELECT statement. The current
260
condition also excludes multi-table update statements.
262
We have to determine whether we will perform subquery materialization
263
before calling the IN=>EXISTS transformation, so that we know whether to
264
perform the whole transformation or only that part of it which wraps
265
Item_in_subselect in an Item_in_optimizer.
267
if (do_materialize &&
269
!select_lex->master_unit()->first_select()->next_select() && // 2
270
select_lex->master_unit()->first_select()->leaf_tables && // 3
271
session->lex->sql_command == SQLCOM_SELECT) // *
273
if (in_subs->is_top_level_item() && // 4
274
!in_subs->is_correlated && // 5
275
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
276
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
279
Item_subselect::trans_res trans_res;
280
if ((trans_res= subselect->select_transformer(this)) !=
281
Item_subselect::RES_OK)
283
return((trans_res == Item_subselect::RES_ERROR));
292
for (ord= order; ord; ord= ord->next)
294
Item *item= *ord->item;
295
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
296
item->split_sum_func(session, ref_pointer_array, all_fields);
300
if (having && having->with_sum_func)
301
having->split_sum_func(session, ref_pointer_array, all_fields,
303
if (select_lex->inner_sum_func_list)
305
Item_sum *end=select_lex->inner_sum_func_list;
306
Item_sum *item_sum= end;
309
item_sum= item_sum->next;
310
item_sum->split_sum_func(session, ref_pointer_array,
311
all_fields, item_sum->ref_by, false);
312
} while (item_sum != end);
315
if (select_lex->inner_refs_list.elements &&
316
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
320
Check if there are references to un-aggregated columns when computing
321
aggregate functions with implicit grouping (there is no GROUP BY).
323
MODE_ONLY_FULL_GROUP_BY is enabled here by default
326
select_lex->full_group_by_flag.test(NON_AGG_FIELD_USED) &&
327
select_lex->full_group_by_flag.test(SUM_FUNC_USED))
329
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
330
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
334
/* Caclulate the number of groups */
336
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
344
* The below will create the new table for
345
* CREATE TABLE ... SELECT
347
* @see create_table_from_items() in drizzled/sql_insert.cc
349
if (result && result->prepare(fields_list, unit_arg))
352
/* Init join struct */
353
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
354
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
355
this->group= group_list != 0;
358
#ifdef RESTRICTED_GROUP
359
if (sum_func_count && !group_list && (func_count || field_count))
361
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
365
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
367
if (alloc_func_list())
377
Remove the predicates pushed down into the subquery
380
Join::remove_subq_pushed_predicates()
381
where IN Must be NULL
382
OUT The remaining WHERE condition, or NULL
385
Given that this join will be executed using (unique|index)_subquery,
386
without "checking NULL", remove the predicates that were pushed down
389
If the subquery compares scalar values, we can remove the condition that
390
was wrapped into trig_cond (it will be checked when needed by the subquery
393
If the subquery compares row values, we need to keep the wrapped
394
equalities in the WHERE clause: when the left (outer) tuple has both NULL
395
and non-NULL values, we'll do a full table scan and will rely on the
396
equalities corresponding to non-NULL parts of left tuple to filter out
397
non-matching records.
399
TODO: We can remove the equalities that will be guaranteed to be true by the
400
fact that subquery engine will be using index lookup. This must be done only
401
for cases where there are no conversion errors of significance, e.g. 257
402
that is searched in a byte. But this requires homogenization of the return
403
codes of all Field*::store() methods.
405
void Join::remove_subq_pushed_predicates(Item **where)
407
if (conds->type() == Item::FUNC_ITEM &&
408
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
409
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
410
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
411
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
412
((Item_func *)conds)->arguments()[0]))
420
global select optimisation.
423
error code saved in field 'error'
432
// to prevent double initialization on EXPLAIN
437
session->set_proc_info("optimizing");
438
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
439
unit->select_limit_cnt);
440
/* select_limit is used to decide if we are likely to scan the whole table */
441
select_limit= unit->select_limit_cnt;
442
if (having || (select_options & OPTION_FOUND_ROWS))
443
select_limit= HA_POS_ERROR;
444
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
445
// Ignore errors of execution if option IGNORE present
446
if (session->lex->ignore)
447
session->lex->current_select->no_error= 1;
449
#ifdef HAVE_REF_TO_FIELDS // Not done yet
450
/* Add HAVING to WHERE if possible */
451
if (having && !group_list && !sum_func_count)
458
else if ((conds=new Item_cond_and(conds,having)))
461
Item_cond_and can't be fixed after creation, so we do not check
464
conds->fix_fields(session, &conds);
465
conds->change_ref_to_fields(session, tables_list);
466
conds->top_level_item();
472
/* Convert all outer joins to inner joins if possible */
473
conds= simplify_joins(this, join_list, conds, true);
474
build_bitmap_for_nested_joins(join_list, 0);
476
conds= optimize_cond(this, conds, join_list, &cond_value);
477
if (session->is_error())
484
having= optimize_cond(this, having, join_list, &having_value);
485
if (session->is_error())
490
if (select_lex->where)
491
select_lex->cond_value= cond_value;
492
if (select_lex->having)
493
select_lex->having_value= having_value;
495
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
496
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
497
{ /* Impossible cond */
498
zero_result_cause= having_value == Item::COND_FALSE ?
499
"Impossible HAVING" : "Impossible WHERE";
501
goto setup_subq_exit;
505
/* Optimize count(*), cmin() and cmax() */
506
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
510
optimizer::sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
511
to the WHERE conditions,
512
or 1 if all items were resolved,
513
or 0, or an error number HA_ERR_...
515
if ((res= optimizer::sum_query(select_lex->leaf_tables, all_fields, conds)))
517
if (res == HA_ERR_KEY_NOT_FOUND)
519
zero_result_cause= "No matching min/max row";
521
goto setup_subq_exit;
530
zero_result_cause= "No matching min/max row";
532
goto setup_subq_exit;
534
zero_result_cause= "Select tables optimized away";
535
tables_list= 0; // All tables resolved
536
const_tables= tables;
538
Extract all table-independent conditions and replace the WHERE
539
clause with them. All other conditions were computed by optimizer::sum_query
540
and the MIN/MAX/COUNT function(s) have been replaced by constants,
541
so there is no need to compute the whole WHERE clause again.
542
Notice that make_cond_for_table() will always succeed to remove all
543
computed conditions, because optimizer::sum_query() is applicable only to
545
Preserve conditions for EXPLAIN.
547
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
549
COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
550
conds= table_independent_conds;
552
goto setup_subq_exit;
560
error= -1; // Error is sent to client
561
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
563
/* Calculate how to do the join */
564
session->set_proc_info("statistics");
565
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
566
session->is_fatal_error)
571
/* Remove distinct if only const tables */
572
select_distinct= select_distinct && (const_tables != tables);
573
session->set_proc_info("preparing");
574
if (result->initialize_tables(this))
576
return 1; // error == -1
578
if (const_table_map != found_const_table_map &&
579
!(select_options & SELECT_DESCRIBE) &&
581
!(conds->used_tables() & RAND_TABLE_BIT) ||
582
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
584
zero_result_cause= "no matching row in const table";
585
goto setup_subq_exit;
587
if (!(session->options & OPTION_BIG_SELECTS) &&
588
best_read > (double) session->variables.max_join_size &&
589
!(select_options & SELECT_DESCRIBE))
591
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
595
if (const_tables && !(select_options & SELECT_NO_UNLOCK))
596
mysql_unlock_some_tables(session, table, const_tables);
597
if (!conds && outer_join)
599
/* Handle the case where we have an OUTER JOIN without a WHERE */
600
conds=new Item_int((int64_t) 1,1); // Always true
602
select= optimizer::make_select(*table, const_table_map,
603
const_table_map, conds, 1, &error);
610
reset_nj_counters(join_list);
611
make_outerjoin_info(this);
614
Among the equal fields belonging to the same multiple equality
615
choose the one that is to be retrieved first and substitute
616
all references to these in where condition for a reference for
621
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
622
conds->update_used_tables();
626
Permorm the the optimization on fields evaluation mentioned above
627
for all on expressions.
629
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
631
if (*tab->on_expr_ref)
633
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
636
(*tab->on_expr_ref)->update_used_tables();
640
if (conds &&!outer_join && const_table_map != found_const_table_map &&
641
(select_options & SELECT_DESCRIBE) &&
642
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
644
conds=new Item_int((int64_t) 0,1); // Always false
647
if (make_join_select(this, select, conds))
650
"Impossible WHERE noticed after reading const tables";
651
goto setup_subq_exit;
654
error= -1; /* if goto err */
656
/* Optimize distinct away if possible */
658
order_st *org_order= order;
659
order= remove_constants(this, order,conds,1, &simple_order);
660
if (session->is_error())
667
If we are using ORDER BY NULL or ORDER BY const_expression,
668
return result in any order (even if we are using a GROUP BY)
670
if (!order && org_order)
674
Check if we can optimize away GROUP BY/DISTINCT.
675
We can do that if there are no aggregate functions, the
676
fields in DISTINCT clause (if present) and/or columns in GROUP BY
677
(if present) contain direct references to all key parts of
678
an unique index (in whatever order) and if the key parts of the
679
unique index cannot contain NULLs.
680
Note that the unique keys for DISTINCT and GROUP BY should not
681
be the same (as long as they are unique).
683
The FROM clause must contain a single non-constant table.
685
if (tables - const_tables == 1 && (group_list || select_distinct) &&
686
! tmp_table_param.sum_func_count &&
687
(! join_tab[const_tables].select ||
688
! join_tab[const_tables].select->quick ||
689
join_tab[const_tables].select->quick->get_type() !=
690
optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))
692
if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
695
We have found that grouping can be removed since groups correspond to
696
only one row anyway, but we still have to guarantee correct result
697
order. The line below effectively rewrites the query from GROUP BY
698
<fields> to ORDER BY <fields>. There are two exceptions:
699
- if skip_sort_order is set (see above), then we can simply skip
701
- we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'
702
with the GROUP BY ones, i.e. either one is a prefix of another.
703
We only check if the ORDER BY is a prefix of GROUP BY. In this case
704
test_if_subpart() copies the ASC/DESC attributes from the original
706
If GROUP BY is a prefix of order_st BY, then it is safe to leave
709
if (! order || test_if_subpart(group_list, order))
710
order= skip_sort_order ? 0 : group_list;
712
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
713
rewritten to IGNORE INDEX FOR order_st BY(fields).
715
join_tab->table->keys_in_use_for_order_by=
716
join_tab->table->keys_in_use_for_group_by;
720
if (select_distinct &&
721
list_contains_unique_index(join_tab[const_tables].table,
722
find_field_in_item_list,
723
(void *) &fields_list))
728
if (group_list || tmp_table_param.sum_func_count)
730
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
733
else if (select_distinct && tables - const_tables == 1)
736
We are only using one table. In this case we change DISTINCT to a
738
- The GROUP BY can be done through indexes (no sort) and the order_st
739
BY only uses selected fields.
740
(In this case we can later optimize away GROUP BY and order_st BY)
741
- We are scanning the whole table without LIMIT
743
- We are using CALC_FOUND_ROWS
744
- We are using an ORDER BY that can't be optimized away.
746
We don't want to use this optimization when we are using LIMIT
747
because in this case we can just create a temporary table that
748
holds LIMIT rows and stop when this table is full.
750
JoinTable *tab= &join_tab[const_tables];
751
bool all_order_fields_used;
753
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
754
&tab->table->keys_in_use_for_order_by);
755
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
756
order, fields_list, all_fields,
757
&all_order_fields_used)))
759
bool skip_group= (skip_sort_order &&
760
test_if_skip_sort_order(tab, group_list, select_limit, 1,
761
&tab->table->keys_in_use_for_group_by) != 0);
762
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
763
if ((skip_group && all_order_fields_used) ||
764
select_limit == HA_POS_ERROR ||
765
(order && !skip_sort_order))
767
/* Change DISTINCT to GROUP BY */
770
if (all_order_fields_used)
772
if (order && skip_sort_order)
775
Force MySQL to read the table in sorted order to get result in
778
tmp_table_param.quick_group=0;
782
group=1; // For end_write_group
787
else if (session->is_fatal_error) // End of memory
792
order_st *old_group_list;
793
group_list= remove_constants(this, (old_group_list= group_list), conds,
794
rollup.state == ROLLUP::STATE_NONE,
796
if (session->is_error())
801
if (old_group_list && !group_list)
804
if (!group_list && group)
806
order=0; // The output has only one row
808
select_distinct= 0; // No need in distinct for 1 row
809
group_optimized_away= 1;
812
calc_group_buffer(this, group_list);
813
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
815
if (test_if_subpart(group_list, order) ||
816
(!group_list && tmp_table_param.sum_func_count))
819
// Can't use sort on head table if using row cache
829
Check if we need to create a temporary table.
830
This has to be done if all tables are not already read (const tables)
831
and one of the following conditions holds:
832
- We are using DISTINCT (simple distinct's are already optimized away)
833
- We are using an ORDER BY or GROUP BY on fields not in the first table
834
- We are using different ORDER BY and GROUP BY orders
835
- The user wants us to buffer the result.
837
need_tmp= (const_tables != tables &&
838
((select_distinct || !simple_order || !simple_group) ||
839
(group_list && order) ||
840
test(select_options & OPTION_BUFFER_RESULT)));
842
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
843
if (make_join_readinfo(this))
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())
1118
/* Even with zero matching rows, subqueries in the HAVING clause
1119
may need to be evaluated if there are aggregate functions in the query.
1121
if (setup_subquery_materialization())
1128
Restore values in temporary join.
1130
void Join::restore_tmp()
1132
memcpy(tmp_join, this, (size_t) sizeof(Join));
1137
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1138
select_lex->offset_limit->val_uint() :
1143
if (exec_tmp_table1)
1145
exec_tmp_table1->cursor->extra(HA_EXTRA_RESET_STATE);
1146
exec_tmp_table1->cursor->ha_delete_all_rows();
1147
exec_tmp_table1->free_io_cache();
1148
exec_tmp_table1->filesort_free_buffers();
1150
if (exec_tmp_table2)
1152
exec_tmp_table2->cursor->extra(HA_EXTRA_RESET_STATE);
1153
exec_tmp_table2->cursor->ha_delete_all_rows();
1154
exec_tmp_table2->free_io_cache();
1155
exec_tmp_table2->filesort_free_buffers();
1158
set_items_ref_array(items0);
1161
memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);
1166
/* Reset of sum functions */
1169
Item_sum *func, **func_ptr= sum_funcs;
1170
while ((func= *(func_ptr++)))
1178
@brief Save the original join layout
1180
@details Saves the original join layout so it can be reused in
1181
re-execution and for EXPLAIN.
1183
@return Operation status
1185
@retval 1 error occurred.
1187
bool Join::init_save_join_tab()
1189
if (!(tmp_join= (Join*)session->alloc(sizeof(Join))))
1191
error= 0; // Ensure that tmp_join.error= 0
1196
bool Join::save_join_tab()
1198
if (!join_tab_save && select_lex->master_unit()->uncacheable)
1200
if (!(join_tab_save= (JoinTable*)session->memdup((unsigned char*) join_tab,
1201
sizeof(JoinTable) * tables)))
1211
Note, that create_sort_index calls test_if_skip_sort_order and may
1212
finally replace sorting with index scan if there is a LIMIT clause in
1213
the query. It's never shown in EXPLAIN!
1216
When can we have here session->net.report_error not zero?
1220
List<Item> *columns_list= &fields_list;
1223
session->set_proc_info("executing");
1226
if (!tables_list && (tables || !select_lex->with_sum_func))
1228
/* Only test of functions */
1229
if (select_options & SELECT_DESCRIBE)
1231
optimizer::ExplainPlan planner(this,
1235
(zero_result_cause ? zero_result_cause : "No tables used"));
1236
planner.printPlan();
1240
result->send_fields(*columns_list);
1242
We have to test for 'conds' here as the WHERE may not be constant
1243
even if we don't have any tables for prepared statements or if
1244
conds uses something like 'rand()'.
1246
if (cond_value != Item::COND_FALSE &&
1247
(!conds || conds->val_int()) &&
1248
(!having || having->val_int()))
1250
if (do_send_rows && result->send_data(fields_list))
1254
error= (int) result->send_eof();
1255
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
1260
error= (int) result->send_eof();
1264
/* Single select (without union) always returns 0 or 1 row */
1265
session->limit_found_rows= send_records;
1266
session->examined_row_count= 0;
1270
Don't reset the found rows count if there're no tables as
1271
FOUND_ROWS() may be called. Never reset the examined row count here.
1272
It must be accumulated from all join iterations of all join parts.
1275
session->limit_found_rows= 0;
1277
if (zero_result_cause)
1279
(void) return_zero_rows(this, result, select_lex->leaf_tables,
1281
send_row_on_empty_set(),
1288
if (select_options & SELECT_DESCRIBE)
1291
Check if we managed to optimize ORDER BY away and don't use temporary
1292
table to resolve order_st BY: in that case, we only may need to do
1293
filesort for GROUP BY.
1295
if (!order && !no_order && (!skip_sort_order || !need_tmp))
1297
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
1299
simple_order= simple_group;
1302
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
1304
if (const_tables == tables
1305
|| ((simple_order || skip_sort_order)
1306
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
1310
optimizer::ExplainPlan planner(this,
1312
order != 0 && ! skip_sort_order,
1314
! tables ? "No tables used" : NULL);
1315
planner.printPlan();
1319
Join *curr_join= this;
1320
List<Item> *curr_all_fields= &all_fields;
1321
List<Item> *curr_fields_list= &fields_list;
1322
Table *curr_tmp_table= 0;
1324
Initialize examined rows here because the values from all join parts
1325
must be accumulated in examined_row_count. Hence every join
1326
iteration must count from zero.
1328
curr_join->examined_rows= 0;
1330
/* Create a tmp table if distinct or if the sort is too complicated */
1336
We are in a non cacheable sub query. Get the saved join structure
1338
(curr_join may have been modified during last exection and we need
1341
curr_join= tmp_join;
1343
curr_tmp_table= exec_tmp_table1;
1345
/* Copy data to the temporary table */
1346
session->set_proc_info("Copying to tmp table");
1347
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
1348
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1349
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1354
curr_tmp_table->cursor->info(HA_STATUS_VARIABLE);
1356
if (curr_join->having)
1357
curr_join->having= curr_join->tmp_having= 0; // Allready done
1359
/* Change sum_fields reference to calculated fields in tmp_table */
1360
curr_join->all_fields= *curr_all_fields;
1363
items1= items0 + all_fields.elements;
1364
if (sort_and_group || curr_tmp_table->group)
1366
if (change_to_use_tmp_fields(session, items1,
1367
tmp_fields_list1, tmp_all_fields1,
1368
fields_list.elements, all_fields))
1373
if (change_refs_to_tmp_fields(session, items1,
1374
tmp_fields_list1, tmp_all_fields1,
1375
fields_list.elements, all_fields))
1378
curr_join->tmp_all_fields1= tmp_all_fields1;
1379
curr_join->tmp_fields_list1= tmp_fields_list1;
1380
curr_join->items1= items1;
1382
curr_all_fields= &tmp_all_fields1;
1383
curr_fields_list= &tmp_fields_list1;
1384
curr_join->set_items_ref_array(items1);
1386
if (sort_and_group || curr_tmp_table->group)
1388
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
1389
+ curr_join->tmp_table_param.func_count;
1390
curr_join->tmp_table_param.sum_func_count= 0;
1391
curr_join->tmp_table_param.func_count= 0;
1395
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
1396
curr_join->tmp_table_param.func_count= 0;
1399
if (curr_tmp_table->group)
1400
{ // Already grouped
1401
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
1402
curr_join->order= curr_join->group_list; /* order by group */
1403
curr_join->group_list= 0;
1407
If we have different sort & group then we must sort the data by group
1408
and copy it to another tmp table
1409
This code is also used if we are using distinct something
1410
we haven't been able to store in the temporary table yet
1411
like SEC_TO_TIME(SUM(...)).
1414
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
1415
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
1416
{ /* Must copy to another table */
1417
/* Free first data from old join */
1418
curr_join->join_free();
1419
if (make_simple_join(curr_join, curr_tmp_table))
1421
calc_group_buffer(curr_join, group_list);
1422
count_field_types(select_lex, &curr_join->tmp_table_param,
1423
curr_join->tmp_all_fields1,
1424
curr_join->select_distinct && !curr_join->group_list);
1425
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
1426
- curr_join->tmp_fields_list1.elements;
1428
if (exec_tmp_table2)
1430
curr_tmp_table= exec_tmp_table2;
1434
/* group data to new table */
1437
If the access method is loose index scan then all MIN/MAX
1438
functions are precomputed, and should be treated as regular
1439
functions. See extended comment in Join::exec.
1441
if (curr_join->join_tab->is_using_loose_index_scan())
1442
curr_join->tmp_table_param.precomputed_group_by= true;
1444
if (!(curr_tmp_table=
1445
exec_tmp_table2= create_tmp_table(session,
1446
&curr_join->tmp_table_param,
1449
curr_join->select_distinct &&
1450
!curr_join->group_list,
1451
1, curr_join->select_options,
1458
curr_join->exec_tmp_table2= exec_tmp_table2;
1460
if (curr_join->group_list)
1462
session->set_proc_info("Creating sort index");
1463
if (curr_join->join_tab == join_tab && save_join_tab())
1467
if (create_sort_index(session, curr_join, curr_join->group_list,
1468
HA_POS_ERROR, HA_POS_ERROR, false) ||
1469
make_group_fields(this, curr_join))
1473
sortorder= curr_join->sortorder;
1476
session->set_proc_info("Copying to group table");
1478
if (curr_join != this)
1482
curr_join->sum_funcs= sum_funcs2;
1483
curr_join->sum_funcs_end= sum_funcs_end2;
1487
curr_join->alloc_func_list();
1488
sum_funcs2= curr_join->sum_funcs;
1489
sum_funcs_end2= curr_join->sum_funcs_end;
1492
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
1494
curr_join->group_list= 0;
1496
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
1497
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1499
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
1500
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1505
curr_join->join_tab->read_record.end_read_record();
1506
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1507
curr_join->join_tab[0].table= 0; // Table is freed
1509
// No sum funcs anymore
1512
items2= items1 + all_fields.elements;
1513
if (change_to_use_tmp_fields(session, items2,
1514
tmp_fields_list2, tmp_all_fields2,
1515
fields_list.elements, tmp_all_fields1))
1517
curr_join->tmp_fields_list2= tmp_fields_list2;
1518
curr_join->tmp_all_fields2= tmp_all_fields2;
1520
curr_fields_list= &curr_join->tmp_fields_list2;
1521
curr_all_fields= &curr_join->tmp_all_fields2;
1522
curr_join->set_items_ref_array(items2);
1523
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
1524
curr_join->tmp_table_param.sum_func_count= 0;
1526
if (curr_tmp_table->distinct)
1527
curr_join->select_distinct=0; /* Each row is unique */
1529
curr_join->join_free(); /* Free quick selects */
1530
if (curr_join->select_distinct && ! curr_join->group_list)
1532
session->set_proc_info("Removing duplicates");
1533
if (curr_join->tmp_having)
1534
curr_join->tmp_having->update_used_tables();
1536
if (remove_duplicates(curr_join, curr_tmp_table,
1537
*curr_fields_list, curr_join->tmp_having))
1540
curr_join->tmp_having=0;
1541
curr_join->select_distinct=0;
1543
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
1544
if (make_simple_join(curr_join, curr_tmp_table))
1546
calc_group_buffer(curr_join, curr_join->group_list);
1547
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
1551
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
1553
if (make_group_fields(this, curr_join))
1559
init_items_ref_array();
1560
items3= ref_pointer_array + (all_fields.elements*4);
1561
setup_copy_fields(session, &curr_join->tmp_table_param,
1562
items3, tmp_fields_list3, tmp_all_fields3,
1563
curr_fields_list->elements, *curr_all_fields);
1564
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
1565
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
1566
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
1567
curr_join->tmp_all_fields3= tmp_all_fields3;
1568
curr_join->tmp_fields_list3= tmp_fields_list3;
1572
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
1573
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
1574
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
1576
curr_fields_list= &tmp_fields_list3;
1577
curr_all_fields= &tmp_all_fields3;
1578
curr_join->set_items_ref_array(items3);
1580
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1582
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
1583
session->is_fatal_error)
1586
if (curr_join->group_list || curr_join->order)
1588
session->set_proc_info("Sorting result");
1589
/* If we have already done the group, add HAVING to sorted table */
1590
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
1592
// Some tables may have been const
1593
curr_join->tmp_having->update_used_tables();
1594
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];
1595
table_map used_tables= (curr_join->const_table_map |
1596
curr_table->table->map);
1598
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
1599
if (sort_table_cond)
1601
if (!curr_table->select)
1602
if (!(curr_table->select= new optimizer::SqlSelect))
1604
if (!curr_table->select->cond)
1605
curr_table->select->cond= sort_table_cond;
1606
else // This should never happen
1608
if (!(curr_table->select->cond=
1609
new Item_cond_and(curr_table->select->cond,
1613
Item_cond_and do not need fix_fields for execution, its parameters
1614
are fixed or do not need fix_fields, too
1616
curr_table->select->cond->quick_fix_field();
1618
curr_table->select_cond= curr_table->select->cond;
1619
curr_table->select_cond->top_level_item();
1620
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
1627
curr_join->select_limit= HA_POS_ERROR;
1631
We can abort sorting after session->select_limit rows if we there is no
1632
WHERE clause for any tables after the sorted one.
1634
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
1635
JoinTable *end_table= &curr_join->join_tab[curr_join->tables];
1636
for (; curr_table < end_table ; curr_table++)
1639
table->keyuse is set in the case there was an original WHERE clause
1640
on the table that was optimized away.
1642
if (curr_table->select_cond ||
1643
(curr_table->keyuse && !curr_table->first_inner))
1645
/* We have to sort all rows */
1646
curr_join->select_limit= HA_POS_ERROR;
1651
if (curr_join->join_tab == join_tab && save_join_tab())
1654
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
1655
chose FILESORT to be faster than INDEX SCAN or there is no
1656
suitable index present.
1657
Note, that create_sort_index calls test_if_skip_sort_order and may
1658
finally replace sorting with index scan if there is a LIMIT clause in
1659
the query. XXX: it's never shown in EXPLAIN!
1660
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
1662
if (create_sort_index(session, curr_join,
1663
curr_join->group_list ?
1664
curr_join->group_list : curr_join->order,
1665
curr_join->select_limit,
1666
(select_options & OPTION_FOUND_ROWS ?
1667
HA_POS_ERROR : unit->select_limit_cnt),
1668
curr_join->group_list ? true : false))
1671
sortorder= curr_join->sortorder;
1672
if (curr_join->const_tables != curr_join->tables &&
1673
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
1676
If no IO cache exists for the first table then we are using an
1677
INDEX SCAN and no filesort. Thus we should not remove the sorted
1678
attribute on the INDEX SCAN.
1684
/* XXX: When can we have here session->is_error() not zero? */
1685
if (session->is_error())
1687
error= session->is_error();
1690
curr_join->having= curr_join->tmp_having;
1691
curr_join->fields= curr_fields_list;
1693
session->set_proc_info("Sending data");
1694
result->send_fields(*curr_fields_list);
1695
error= do_select(curr_join, curr_fields_list, NULL);
1696
session->limit_found_rows= curr_join->send_records;
1698
/* Accumulate the counts from all join iterations of all join parts. */
1699
session->examined_row_count+= curr_join->examined_rows;
1702
With EXPLAIN EXTENDED we have to restore original ref_array
1703
for a derived table which is always materialized.
1704
Otherwise we would not be able to print the query correctly.
1706
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
1707
set_items_ref_array(items0);
1716
Return error that hold Join.
1720
select_lex->join= 0;
1724
if (join_tab != tmp_join->join_tab)
1726
JoinTable *tab, *end;
1727
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
1730
tmp_join->tmp_join= 0;
1731
tmp_table_param.copy_field=0;
1732
return(tmp_join->destroy());
1737
exec_tmp_table1= NULL;
1738
exec_tmp_table2= NULL;
1740
delete_dynamic(&keyuse);
1746
Setup for execution all subqueries of a query, for which the optimizer
1747
chose hash semi-join.
1749
@details Iterate over all subqueries of the query, and if they are under an
1750
IN predicate, and the optimizer chose to compute it via hash semi-join:
1751
- try to initialize all data structures needed for the materialized execution
1752
of the IN predicate,
1753
- if this fails, then perform the IN=>EXISTS transformation which was
1754
previously blocked during Join::prepare.
1756
This method is part of the "code generation" query processing phase.
1758
This phase must be called after substitute_for_best_equal_field() because
1759
that function may replace items with other items from a multiple equality,
1760
and we need to reference the correct items in the index access method of the
1763
@return Operation status
1764
@retval false success.
1765
@retval true error occurred.
1767
bool Join::setup_subquery_materialization()
1769
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1770
un= un->next_unit())
1772
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
1774
Item_subselect *subquery_predicate= sl->master_unit()->item;
1775
if (subquery_predicate &&
1776
subquery_predicate->substype() == Item_subselect::IN_SUBS)
1778
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
1779
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
1780
in_subs->setup_engine())
1789
Partially cleanup Join after it has executed: close index or rnd read
1790
(table cursors), free quick selects.
1792
This function is called in the end of execution of a Join, before the used
1793
tables are unlocked and closed.
1795
For a join that is resolved using a temporary table, the first sweep is
1796
performed against actual tables and an intermediate result is inserted
1797
into the temprorary table.
1798
The last sweep is performed against the temporary table. Therefore,
1799
the base tables and associated buffers used to fill the temporary table
1800
are no longer needed, and this function is called to free them.
1802
For a join that is performed without a temporary table, this function
1803
is called after all rows are sent, but before EOF packet is sent.
1805
For a simple SELECT with no subqueries this function performs a full
1806
cleanup of the Join and calls mysql_unlock_read_tables to free used base
1809
If a Join is executed for a subquery or if it has a subquery, we can't
1810
do the full cleanup and need to do a partial cleanup only.
1811
- If a Join is not the top level join, we must not unlock the tables
1812
because the outer select may not have been evaluated yet, and we
1813
can't unlock only selected tables of a query.
1814
- Additionally, if this Join corresponds to a correlated subquery, we
1815
should not free quick selects and join buffers because they will be
1816
needed for the next execution of the correlated subquery.
1817
- However, if this is a Join for a [sub]select, which is not
1818
a correlated subquery itself, but has subqueries, we can free it
1819
fully and also free Joins of all its subqueries. The exception
1820
is a subquery in SELECT list, e.g: @n
1821
SELECT a, (select cmax(b) from t1) group by c @n
1822
This subquery will not be evaluated at first sweep and its value will
1823
not be inserted into the temporary table. Instead, it's evaluated
1824
when selecting from the temporary table. Therefore, it can't be freed
1825
here even though it's not correlated.
1828
Unlock tables even if the join isn't top level select in the tree
1830
void Join::join_free()
1832
Select_Lex_Unit *tmp_unit;
1835
Optimization: if not EXPLAIN and we are done with the Join,
1838
bool full= (!select_lex->uncacheable && !session->lex->describe);
1839
bool can_unlock= full;
1843
for (tmp_unit= select_lex->first_inner_unit();
1845
tmp_unit= tmp_unit->next_unit())
1846
for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
1848
Item_subselect *subselect= sl->master_unit()->item;
1849
bool full_local= full && (!subselect || subselect->is_evaluated());
1851
If this join is evaluated, we can fully clean it up and clean up all
1852
its underlying joins even if they are correlated -- they will not be
1853
used any more anyway.
1854
If this join is not yet evaluated, we still must clean it up to
1855
close its table cursors -- it may never get evaluated, as in case of
1856
... HAVING false OR a IN (SELECT ...))
1857
but all table cursors must be closed before the unlock.
1859
sl->cleanup_all_joins(full_local);
1860
/* Can't unlock if at least one Join is still needed */
1861
can_unlock= can_unlock && full_local;
1865
We are not using tables anymore
1866
Unlock all tables. We may be in an INSERT .... SELECT statement.
1868
if (can_unlock && lock && session->lock &&
1869
!(select_options & SELECT_NO_UNLOCK) &&
1870
!select_lex->subquery_in_having &&
1871
(select_lex == (session->lex->unit.fake_select_lex ?
1872
session->lex->unit.fake_select_lex : &session->lex->select_lex)))
1875
TODO: unlock tables even if the join isn't top level select in the
1878
mysql_unlock_read_tables(session, lock); // Don't free join->lock
1887
Free resources of given join.
1889
@param fill true if we should free all resources, call with full==1
1890
should be last, before it this function can be called with
1894
With subquery this function definitely will be called several times,
1895
but even for simple query it can be called several times.
1897
void Join::cleanup(bool full)
1901
JoinTable *tab,*end;
1903
Only a sorted table may be cached. This sorted table is always the
1904
first non const table in join->table
1906
if (tables > const_tables) // Test for not-const tables
1908
table[const_tables]->free_io_cache();
1909
table[const_tables]->filesort_free_buffers(full);
1914
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1920
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1923
tab->table->cursor->ha_index_or_rnd_end();
1928
We are not using tables anymore
1929
Unlock all tables. We may be in an INSERT .... SELECT statement.
1934
tmp_table_param.copy_field= 0;
1935
group_fields.delete_elements();
1937
We can't call delete_elements() on copy_funcs as this will cause
1938
problems in free_elements() as some of the elements are then deleted.
1940
tmp_table_param.copy_funcs.empty();
1942
If we have tmp_join and 'this' Join is not tmp_join and
1943
tmp_table_param.copy_field's of them are equal then we have to remove
1944
pointer to tmp_table_param.copy_field from tmp_join, because it qill
1945
be removed in tmp_table_param.cleanup().
1949
tmp_join->tmp_table_param.copy_field ==
1950
tmp_table_param.copy_field)
1952
tmp_join->tmp_table_param.copy_field=
1953
tmp_join->tmp_table_param.save_copy_field= 0;
1955
tmp_table_param.cleanup();
1961
used only in Join::clear
1963
static void clear_tables(Join *join)
1966
must clear only the non-const tables, as const tables
1967
are not re-calculated.
1969
for (uint32_t i= join->const_tables; i < join->tables; i++)
1970
join->table[i]->mark_as_null_row(); // All fields are NULL
1974
Make an array of pointers to sum_functions to speed up
1975
sum_func calculation.
1982
bool Join::alloc_func_list()
1984
uint32_t func_count, group_parts;
1986
func_count= tmp_table_param.sum_func_count;
1988
If we are using rollup, we need a copy of the summary functions for
1991
if (rollup.state != ROLLUP::STATE_NONE)
1992
func_count*= (send_group_parts+1);
1994
group_parts= send_group_parts;
1996
If distinct, reserve memory for possible
1997
disctinct->group_by optimization
1999
if (select_distinct)
2001
group_parts+= fields_list.elements;
2003
If the order_st clause is specified then it's possible that
2004
it also will be optimized, so reserve space for it too
2009
for (ord= order; ord; ord= ord->next)
2014
/* This must use calloc() as rollup_make_fields depends on this */
2015
sum_funcs= (Item_sum**) session->calloc(sizeof(Item_sum**) * (func_count+1) +
2016
sizeof(Item_sum***) * (group_parts+1));
2017
sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
2018
return(sum_funcs == 0);
2022
Initialize 'sum_funcs' array with all Item_sum objects.
2024
@param field_list All items
2025
@param send_fields Items in select list
2026
@param before_group_by Set to 1 if this is called before GROUP BY handling
2027
@param recompute Set to true if sum_funcs must be recomputed
2034
bool Join::make_sum_func_list(List<Item> &field_list,
2035
List<Item> &send_fields,
2036
bool before_group_by,
2039
List_iterator_fast<Item> it(field_list);
2043
if (*sum_funcs && !recompute)
2044
return(false); /* We have already initialized sum_funcs. */
2049
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2050
(!((Item_sum*) item)->depended_from() ||
2051
((Item_sum *)item)->depended_from() == select_lex))
2052
*func++= (Item_sum*) item;
2054
if (before_group_by && rollup.state == ROLLUP::STATE_INITED)
2056
rollup.state= ROLLUP::STATE_READY;
2057
if (rollup_make_fields(field_list, send_fields, &func))
2058
return(true); // Should never happen
2060
else if (rollup.state == ROLLUP::STATE_NONE)
2062
for (uint32_t i=0 ; i <= send_group_parts ;i++)
2063
sum_funcs_end[i]= func;
2065
else if (rollup.state == ROLLUP::STATE_READY)
2066
return(false); // Don't put end marker
2067
*func=0; // End marker
2071
/** Allocate memory needed for other rollup functions. */
2072
bool Join::rollup_init()
2077
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2078
rollup.state= ROLLUP::STATE_INITED;
2081
Create pointers to the different sum function groups
2082
These are updated by rollup_make_fields()
2084
tmp_table_param.group_parts= send_group_parts;
2086
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
2088
sizeof(List<Item>) +
2089
ref_pointer_array_size)
2090
* send_group_parts )))
2093
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
2094
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
2095
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
2098
Prepare space for field list for the different levels
2099
These will be filled up in rollup_make_fields()
2101
for (i= 0 ; i < send_group_parts ; i++)
2103
rollup.null_items[i]= new (session->mem_root) Item_null_result();
2104
List<Item> *rollup_fields= &rollup.fields[i];
2105
rollup_fields->empty();
2106
rollup.ref_pointer_arrays[i]= ref_array;
2107
ref_array+= all_fields.elements;
2109
for (i= 0 ; i < send_group_parts; i++)
2111
for (j=0 ; j < fields_list.elements ; j++)
2112
rollup.fields[i].push_back(rollup.null_items[i]);
2114
List_iterator<Item> it(all_fields);
2116
while ((item= it++))
2118
order_st *group_tmp;
2119
bool found_in_group= 0;
2121
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2123
if (*group_tmp->item == item)
2125
item->maybe_null= 1;
2127
if (item->const_item())
2130
For ROLLUP queries each constant item referenced in GROUP BY list
2131
is wrapped up into an Item_func object yielding the same value
2132
as the constant item. The objects of the wrapper class are never
2133
considered as constant items and besides they inherit all
2134
properties of the Item_result_field class.
2135
This wrapping allows us to ensure writing constant items
2136
into temporary tables whenever the result of the ROLLUP
2137
operation has to be written into a temporary table, e.g. when
2138
ROLLUP is used together with DISTINCT in the SELECT list.
2139
Usually when creating temporary tables for a intermidiate
2140
result we do not include fields for constant expressions.
2142
Item* new_item= new Item_func_rollup_const(item);
2145
new_item->fix_fields(session, (Item **) 0);
2146
session->change_item_tree(it.ref(), new_item);
2147
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
2149
if (*tmp->item == item)
2150
session->change_item_tree(tmp->item, new_item);
2155
if (item->type() == Item::FUNC_ITEM && !found_in_group)
2157
bool changed= false;
2158
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
2161
We have to prevent creation of a field in a temporary table for
2162
an expression that contains GROUP BY attributes.
2163
Marking the expression item as 'with_sum_func' will ensure this.
2166
item->with_sum_func= 1;
2173
Fill up rollup structures with pointers to fields to use.
2175
Creates copies of item_sum items for each sum level.
2177
@param fields_arg List of all fields (hidden and real ones)
2178
@param sel_fields Pointer to selected fields
2179
@param func Store here a pointer to all fields
2183
In this case func is pointing to next not used element.
2187
bool Join::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2189
List_iterator_fast<Item> it(fields_arg);
2190
Item *first_field= sel_fields.head();
2194
Create field lists for the different levels
2196
The idea here is to have a separate field list for each rollup level to
2197
avoid all runtime checks of which columns should be NULL.
2199
The list is stored in reverse order to get sum function in such an order
2200
in func that it makes it easy to reset them with init_sum_functions()
2202
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2204
rollup.fields[0] will contain list where a,b,c is NULL
2205
rollup.fields[1] will contain list where b,c is NULL
2207
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
2209
sum_funcs_end[0] points to all sum functions
2210
sum_funcs_end[1] points to all sum functions, except grand totals
2214
for (level=0 ; level < send_group_parts ; level++)
2217
uint32_t pos= send_group_parts - level -1;
2218
bool real_fields= 0;
2220
List_iterator<Item> new_it(rollup.fields[pos]);
2221
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
2222
order_st *start_group;
2224
/* Point to first hidden field */
2225
Item **ref_array= ref_array_start + fields_arg.elements-1;
2227
/* Remember where the sum functions ends for the previous level */
2228
sum_funcs_end[pos+1]= *func;
2230
/* Find the start of the group for this level */
2231
for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
2235
while ((item= it++))
2237
if (item == first_field)
2239
real_fields= 1; // End of hidden fields
2240
ref_array= ref_array_start;
2243
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2244
(!((Item_sum*) item)->depended_from() ||
2245
((Item_sum *)item)->depended_from() == select_lex))
2249
This is a top level summary function that must be replaced with
2250
a sum function that is reset for this level.
2252
NOTE: This code creates an object which is not that nice in a
2253
sub select. Fortunately it's not common to have rollup in
2256
item= item->copy_or_same(session);
2257
((Item_sum*) item)->make_unique();
2258
*(*func)= (Item_sum*) item;
2263
/* Check if this is something that is part of this group by */
2264
order_st *group_tmp;
2265
for (group_tmp= start_group, i= pos ;
2266
group_tmp ; group_tmp= group_tmp->next, i++)
2268
if (*group_tmp->item == item)
2271
This is an element that is used by the GROUP BY and should be
2272
set to NULL in this level
2274
Item_null_result *null_item= new (session->mem_root) Item_null_result();
2277
item->maybe_null= 1; // Value will be null sometimes
2278
null_item->result_field= item->get_tmp_table_field();
2287
(void) new_it++; // Point to next item
2288
new_it.replace(item); // Replace previous
2295
sum_funcs_end[0]= *func; // Point to last function
2300
Send all rollup levels higher than the current one to the client.
2304
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2307
@param idx Level we are on:
2308
- 0 = Total sum level
2309
- 1 = First group changed (a)
2310
- 2 = Second group changed (a,b)
2315
1 If send_data_failed()
2317
int Join::rollup_send_data(uint32_t idx)
2320
for (i= send_group_parts ; i-- > idx ; )
2322
/* Get reference pointers to sum functions in place */
2323
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2324
ref_pointer_array_size);
2325
if ((!having || having->val_int()))
2327
if (send_records < unit->select_limit_cnt && do_send_rows &&
2328
result->send_data(rollup.fields[i]))
2333
/* Restore ref_pointer_array */
2334
set_items_ref_array(current_ref_pointer_array);
2339
Write all rollup levels higher than the current one to a temp table.
2343
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
2346
@param idx Level we are on:
2347
- 0 = Total sum level
2348
- 1 = First group changed (a)
2349
- 2 = Second group changed (a,b)
2350
@param table reference to temp table
2355
1 if write_data_failed()
2357
int Join::rollup_write_data(uint32_t idx, Table *table_arg)
2360
for (i= send_group_parts ; i-- > idx ; )
2362
/* Get reference pointers to sum functions in place */
2363
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2364
ref_pointer_array_size);
2365
if ((!having || having->val_int()))
2369
List_iterator_fast<Item> it(rollup.fields[i]);
2370
while ((item= it++))
2372
if (item->type() == Item::NULL_ITEM && item->is_result_field())
2373
item->save_in_result_field(1);
2375
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2376
if ((write_error= table_arg->cursor->insertRecord(table_arg->getInsertRecord())))
2378
my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2383
/* Restore ref_pointer_array */
2384
set_items_ref_array(current_ref_pointer_array);
2389
clear results if there are not rows found for group
2390
(end_send_group/end_write_group)
2395
copy_fields(&tmp_table_param);
2399
Item_sum *func, **func_ptr= sum_funcs;
2400
while ((func= *(func_ptr++)))
2406
change select_result object of Join.
2408
@param res new select_result object
2415
bool Join::change_result(select_result *res)
2418
if (result->prepare(fields_list, select_lex->master_unit()))
2426
Cache constant expressions in WHERE, HAVING, ON conditions.
2429
void Join::cache_const_exprs()
2431
bool cache_flag= false;
2432
bool *analyzer_arg= &cache_flag;
2434
/* No need in cache if all tables are constant. */
2435
if (const_tables == tables)
2439
conds->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2440
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2443
having->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2444
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2446
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
2448
if (*tab->on_expr_ref)
2451
(*tab->on_expr_ref)->compile(&Item::cache_const_expr_analyzer,
2452
(unsigned char **)&analyzer_arg,
2453
&Item::cache_const_expr_transformer,
2454
(unsigned char *)&cache_flag);
2462
Process one record of the nested loop join.
2466
This function will evaluate parts of WHERE/ON clauses that are
2467
applicable to the partial record on hand and in case of success
2468
submit this record to the next level of the nested loop.
2470
enum_nested_loop_state evaluate_join_record(Join *join, JoinTable *join_tab, int error)
2472
bool not_used_in_distinct= join_tab->not_used_in_distinct;
2473
ha_rows found_records= join->found_records;
2474
COND *select_cond= join_tab->select_cond;
2476
if (error > 0 || (join->session->is_error())) // Fatal error
2477
return NESTED_LOOP_ERROR;
2479
return NESTED_LOOP_NO_MORE_ROWS;
2480
if (join->session->killed) // Aborted by user
2482
join->session->send_kill_message();
2483
return NESTED_LOOP_KILLED;
2485
if (!select_cond || select_cond->val_int())
2488
There is no select condition or the attached pushed down
2489
condition is true => a match is found.
2492
while (join_tab->first_unmatched && found)
2495
The while condition is always false if join_tab is not
2496
the last inner join table of an outer join operation.
2498
JoinTable *first_unmatched= join_tab->first_unmatched;
2500
Mark that a match for current outer table is found.
2501
This activates push down conditional predicates attached
2502
to the all inner tables of the outer join.
2504
first_unmatched->found= 1;
2505
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2507
if (tab->table->reginfo.not_exists_optimize)
2508
return NESTED_LOOP_NO_MORE_ROWS;
2509
/* Check all predicates that has just been activated. */
2511
Actually all predicates non-guarded by first_unmatched->found
2512
will be re-evaluated again. It could be fixed, but, probably,
2513
it's not worth doing now.
2515
if (tab->select_cond && !tab->select_cond->val_int())
2517
/* The condition attached to table tab is false */
2518
if (tab == join_tab)
2523
Set a return point if rejected predicate is attached
2524
not to the last table of the current nest level.
2526
join->return_tab= tab;
2527
return NESTED_LOOP_OK;
2532
Check whether join_tab is not the last inner table
2533
for another embedding outer join.
2535
if ((first_unmatched= first_unmatched->first_upper) &&
2536
first_unmatched->last_inner != join_tab)
2538
join_tab->first_unmatched= first_unmatched;
2541
JoinTable *return_tab= join->return_tab;
2542
join_tab->found_match= true;
2545
It was not just a return to lower loop level when one
2546
of the newly activated predicates is evaluated as false
2547
(See above join->return_tab= tab).
2549
join->examined_rows++;
2550
join->session->row_count++;
2554
enum enum_nested_loop_state rc;
2555
/* A match from join_tab is found for the current partial join. */
2556
rc= (*join_tab->next_select)(join, join_tab+1, 0);
2557
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2559
if (return_tab < join->return_tab)
2560
join->return_tab= return_tab;
2562
if (join->return_tab < join_tab)
2563
return NESTED_LOOP_OK;
2565
Test if this was a SELECT DISTINCT query on a table that
2566
was not in the field list; In this case we can abort if
2567
we found a row, as no new rows can be added to the result.
2569
if (not_used_in_distinct && found_records != join->found_records)
2570
return NESTED_LOOP_NO_MORE_ROWS;
2573
join_tab->read_record.cursor->unlock_row();
2578
The condition pushed down to the table join_tab rejects all rows
2579
with the beginning coinciding with the current partial join.
2581
join->examined_rows++;
2582
join->session->row_count++;
2583
join_tab->read_record.cursor->unlock_row();
2585
return NESTED_LOOP_OK;
2590
Construct a NULL complimented partial join record and feed it to the next
2591
level of the nested loop. This function is used in case we have
2592
an OUTER join and no matching record was found.
2594
enum_nested_loop_state evaluate_null_complemented_join_record(Join *join, JoinTable *join_tab)
2597
The table join_tab is the first inner table of a outer join operation
2598
and no matches has been found for the current outer row.
2600
JoinTable *last_inner_tab= join_tab->last_inner;
2601
/* Cache variables for faster loop */
2603
for ( ; join_tab <= last_inner_tab ; join_tab++)
2605
/* Change the the values of guard predicate variables. */
2607
join_tab->not_null_compl= 0;
2608
/* The outer row is complemented by nulls for each inner tables */
2609
join_tab->table->restoreRecordAsDefault(); // Make empty record
2610
join_tab->table->mark_as_null_row(); // For group by without error
2611
select_cond= join_tab->select_cond;
2612
/* Check all attached conditions for inner table rows. */
2613
if (select_cond && !select_cond->val_int())
2614
return NESTED_LOOP_OK;
2618
The row complemented by nulls might be the first row
2619
of embedding outer joins.
2620
If so, perform the same actions as in the code
2621
for the first regular outer join row above.
2625
JoinTable *first_unmatched= join_tab->first_unmatched;
2626
if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
2628
join_tab->first_unmatched= first_unmatched;
2629
if (! first_unmatched)
2631
first_unmatched->found= 1;
2632
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2634
if (tab->select_cond && !tab->select_cond->val_int())
2636
join->return_tab= tab;
2637
return NESTED_LOOP_OK;
2642
The row complemented by nulls satisfies all conditions
2643
attached to inner tables.
2644
Send the row complemented by nulls to be joined with the
2647
return (*join_tab->next_select)(join, join_tab+1, 0);
2650
enum_nested_loop_state flush_cached_records(Join *join, JoinTable *join_tab, bool skip_last)
2652
enum_nested_loop_state rc= NESTED_LOOP_OK;
2656
join_tab->table->null_row= 0;
2657
if (!join_tab->cache.records)
2659
return NESTED_LOOP_OK; /* Nothing to do */
2664
(void) join_tab->cache.store_record_in_cache(); // Must save this for later
2668
if (join_tab->use_quick == 2)
2670
if (join_tab->select->quick)
2671
{ /* Used quick select last. reset it */
2672
delete join_tab->select->quick;
2673
join_tab->select->quick=0;
2676
/* read through all records */
2677
if ((error=join_init_read_record(join_tab)))
2679
join_tab->cache.reset_cache_write();
2680
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2683
for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)
2685
tmp->status=tmp->table->status;
2686
tmp->table->status=0;
2689
info= &join_tab->read_record;
2692
if (join->session->killed)
2694
join->session->send_kill_message();
2695
return NESTED_LOOP_KILLED;
2697
optimizer::SqlSelect *select= join_tab->select;
2698
if (rc == NESTED_LOOP_OK &&
2699
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2702
join_tab->cache.reset_cache_read();
2703
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2705
join_tab->readCachedRecord();
2706
if (!select || !select->skip_record())
2710
rc= (join_tab->next_select)(join,join_tab+1,0);
2711
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2713
join_tab->cache.reset_cache_write();
2718
return NESTED_LOOP_ERROR;
2722
} while (!(error=info->read_record(info)));
2725
join_tab->readCachedRecord(); // Restore current record
2726
join_tab->cache.reset_cache_write();
2727
if (error > 0) // Fatal error
2728
return NESTED_LOOP_ERROR;
2729
for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2730
tmp2->table->status=tmp2->status;
2731
return NESTED_LOOP_OK;
2734
/*****************************************************************************
2736
Functions that end one nested loop iteration. Different functions
2737
are used to support GROUP BY clause and to redirect records
2738
to a table (e.g. in case of SELECT into a temporary table) or to the
2742
NESTED_LOOP_OK - the record has been successfully handled
2743
NESTED_LOOP_ERROR - a fatal error (like table corruption)
2745
NESTED_LOOP_KILLED - thread shutdown was requested while processing
2747
NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;
2748
additionally, the nested loop produced the
2749
number of rows specified in the LIMIT clause
2751
NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
2752
additionally, there is a cursor and the nested
2753
loop algorithm produced the number of rows
2754
that is specified for current cursor fetch
2756
All return values except NESTED_LOOP_OK abort the nested loop.
2757
*****************************************************************************/
2758
enum_nested_loop_state end_send(Join *join, JoinTable *, bool end_of_records)
2760
if (! end_of_records)
2763
if (join->having && join->having->val_int() == 0)
2764
return NESTED_LOOP_OK; // Didn't match having
2766
if (join->do_send_rows)
2767
error=join->result->send_data(*join->fields);
2769
return NESTED_LOOP_ERROR;
2770
if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2772
if (join->select_options & OPTION_FOUND_ROWS)
2774
JoinTable *jt=join->join_tab;
2775
if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2776
&& !join->send_group_parts && !join->having && !jt->select_cond &&
2777
!(jt->select && jt->select->quick) &&
2778
(jt->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
2781
/* Join over all rows in table; Return number of found rows */
2782
Table *table= jt->table;
2784
join->select_options^= OPTION_FOUND_ROWS;
2785
if (table->sort.record_pointers ||
2786
(table->sort.io_cache && my_b_inited(table->sort.io_cache)))
2788
/* Using filesort */
2789
join->send_records= table->sort.found_records;
2793
table->cursor->info(HA_STATUS_VARIABLE);
2794
join->send_records= table->cursor->stats.records;
2799
join->do_send_rows= 0;
2800
if (join->unit->fake_select_lex)
2801
join->unit->fake_select_lex->select_limit= 0;
2802
return NESTED_LOOP_OK;
2805
return NESTED_LOOP_QUERY_LIMIT; // Abort nicely
2807
else if (join->send_records >= join->fetch_limit)
2810
There is a server side cursor and all rows for
2811
this fetch request are sent.
2813
return NESTED_LOOP_CURSOR_LIMIT;
2817
return NESTED_LOOP_OK;
2820
enum_nested_loop_state end_write(Join *join, JoinTable *, bool end_of_records)
2822
Table *table= join->tmp_table;
2824
if (join->session->killed) // Aborted by user
2826
join->session->send_kill_message();
2827
return NESTED_LOOP_KILLED;
2829
if (!end_of_records)
2831
copy_fields(&join->tmp_table_param);
2832
copy_funcs(join->tmp_table_param.items_to_copy);
2833
if (!join->having || join->having->val_int())
2836
join->found_records++;
2837
if ((error=table->cursor->insertRecord(table->getInsertRecord())))
2839
if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))
2842
my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2843
return NESTED_LOOP_ERROR; // Table is_full error
2845
if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
2847
if (!(join->select_options & OPTION_FOUND_ROWS))
2848
return NESTED_LOOP_QUERY_LIMIT;
2849
join->do_send_rows= 0;
2850
join->unit->select_limit_cnt= HA_POS_ERROR;
2851
return NESTED_LOOP_OK;
2856
return NESTED_LOOP_OK;
2859
/** Group by searching after group record and updating it if possible. */
2860
enum_nested_loop_state end_update(Join *join, JoinTable *, bool end_of_records)
2862
Table *table= join->tmp_table;
2867
return NESTED_LOOP_OK;
2868
if (join->session->killed) // Aborted by user
2870
join->session->send_kill_message();
2871
return NESTED_LOOP_KILLED;
2874
join->found_records++;
2875
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2876
/* Make a key of group index */
2877
for (group=table->group ; group ; group=group->next)
2879
Item *item= *group->item;
2880
item->save_org_in_field(group->field);
2881
/* Store in the used key if the field was 0 */
2882
if (item->maybe_null)
2883
group->buff[-1]= (char) group->field->is_null();
2885
if (!table->cursor->index_read_map(table->getUpdateRecord(),
2886
join->tmp_table_param.group_buff,
2889
{ /* Update old record */
2890
table->restoreRecord();
2891
update_tmptable_sum_func(join->sum_funcs,table);
2892
if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
2893
table->getInsertRecord())))
2895
table->print_error(error,MYF(0));
2896
return NESTED_LOOP_ERROR;
2898
return NESTED_LOOP_OK;
2902
Copy null bits from group key to table
2903
We can't copy all data as the key may have different format
2904
as the row data (for example as with VARCHAR keys)
2906
KeyPartInfo *key_part;
2907
for (group=table->group,key_part=table->key_info[0].key_part;
2909
group=group->next,key_part++)
2911
if (key_part->null_bit)
2912
memcpy(table->getInsertRecord()+key_part->offset, group->buff, 1);
2914
init_tmptable_sum_functions(join->sum_funcs);
2915
copy_funcs(join->tmp_table_param.items_to_copy);
2916
if ((error=table->cursor->insertRecord(table->getInsertRecord())))
2918
my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2919
return NESTED_LOOP_ERROR; // Table is_full error
2921
join->send_records++;
2922
return NESTED_LOOP_OK;
2925
/** Like end_update, but this is done with unique constraints instead of keys. */
2926
enum_nested_loop_state end_unique_update(Join *join, JoinTable *, bool end_of_records)
2928
Table *table= join->tmp_table;
2932
return NESTED_LOOP_OK;
2933
if (join->session->killed) // Aborted by user
2935
join->session->send_kill_message();
2936
return NESTED_LOOP_KILLED;
2939
init_tmptable_sum_functions(join->sum_funcs);
2940
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2941
copy_funcs(join->tmp_table_param.items_to_copy);
2943
if (!(error= table->cursor->insertRecord(table->getInsertRecord())))
2944
join->send_records++; // New group
2947
if ((int) table->get_dup_key(error) < 0)
2949
table->print_error(error,MYF(0));
2950
return NESTED_LOOP_ERROR;
2952
if (table->cursor->rnd_pos(table->getUpdateRecord(),table->cursor->dup_ref))
2954
table->print_error(error,MYF(0));
2955
return NESTED_LOOP_ERROR;
2957
table->restoreRecord();
2958
update_tmptable_sum_func(join->sum_funcs,table);
2959
if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
2960
table->getInsertRecord())))
2962
table->print_error(error,MYF(0));
2963
return NESTED_LOOP_ERROR;
2966
return NESTED_LOOP_OK;
2970
allocate group fields or take prepared (cached).
2972
@param main_join join of current select
2973
@param curr_join current join (join of current select or temporary copy
2981
static bool make_group_fields(Join *main_join, Join *curr_join)
2983
if (main_join->group_fields_cache.elements)
2985
curr_join->group_fields= main_join->group_fields_cache;
2986
curr_join->sort_and_group= 1;
2990
if (alloc_group_fields(curr_join, curr_join->group_list))
2992
main_join->group_fields_cache= curr_join->group_fields;
2998
calc how big buffer we need for comparing group entries.
3000
static void calc_group_buffer(Join *join,order_st *group)
3002
uint32_t key_length=0, parts=0, null_parts=0;
3006
for (; group ; group=group->next)
3008
Item *group_item= *group->item;
3009
Field *field= group_item->get_tmp_table_field();
3012
enum_field_types type;
3013
if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
3014
key_length+=MAX_BLOB_WIDTH; // Can't be used as a key
3015
else if (type == DRIZZLE_TYPE_VARCHAR)
3016
key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
3018
key_length+= field->pack_length();
3022
switch (group_item->result_type()) {
3024
key_length+= sizeof(double);
3027
key_length+= sizeof(int64_t);
3029
case DECIMAL_RESULT:
3030
key_length+= my_decimal_get_binary_size(group_item->max_length -
3031
(group_item->decimals ? 1 : 0),
3032
group_item->decimals);
3036
enum enum_field_types type= group_item->field_type();
3038
As items represented as DATE/TIME fields in the group buffer
3039
have STRING_RESULT result type, we increase the length
3040
by 8 as maximum pack length of such fields.
3042
if (type == DRIZZLE_TYPE_DATE ||
3043
type == DRIZZLE_TYPE_DATETIME ||
3044
type == DRIZZLE_TYPE_TIMESTAMP)
3051
Group strings are taken as varstrings and require an length field.
3052
A field is not yet created by create_tmp_field()
3053
and the sizes should match up.
3055
key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3060
/* This case should never be choosen */
3062
my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
3066
if (group_item->maybe_null)
3069
join->tmp_table_param.group_length=key_length+null_parts;
3070
join->tmp_table_param.group_parts=parts;
3071
join->tmp_table_param.group_null_parts=null_parts;
3075
Get a list of buffers for saveing last group.
3077
Groups are saved in reverse order for easyer check loop.
3079
static bool alloc_group_fields(Join *join,order_st *group)
3083
for (; group ; group=group->next)
3085
Cached_item *tmp= new_Cached_item(join->session, *group->item);
3086
if (!tmp || join->group_fields.push_front(tmp))
3090
join->sort_and_group=1; /* Mark for do_select */
3094
static uint32_t cache_record_length(Join *join,uint32_t idx)
3097
JoinTable **pos,**end;
3098
Session *session=join->session;
3100
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
3104
JoinTable *join_tab= *pos;
3105
if (!join_tab->used_fieldlength) /* Not calced yet */
3106
calc_used_field_length(session, join_tab);
3107
length+=join_tab->used_fieldlength;
3113
Get the number of different row combinations for subset of partial join
3117
join The join structure
3118
idx Number of tables in the partial join order (i.e. the
3119
partial join order is in join->positions[0..idx-1])
3120
found_ref Bitmap of tables for which we need to find # of distinct
3124
Given a partial join order (in join->positions[0..idx-1]) and a subset of
3125
tables within that join order (specified in found_ref), find out how many
3126
distinct row combinations of subset tables will be in the result of the
3129
This is used as follows: Suppose we have a table accessed with a ref-based
3130
method. The ref access depends on current rows of tables in found_ref.
3131
We want to count # of different ref accesses. We assume two ref accesses
3132
will be different if at least one of access parameters is different.
3133
Example: consider a query
3135
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
3138
t1, ref access on t1.key=c1
3139
t2, ref access on t2.key=c2
3140
t3, ref access on t3.key=t1.field
3142
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
3143
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
3144
For t3: n_ref_scans = records_read(t1)*records_read(t2)
3145
n_distinct_ref_scans = #records_read(t1)
3147
The reason for having this function (at least the latest version of it)
3148
is that we need to account for buffering in join execution.
3150
An edge-case example: if we have a non-first table in join accessed via
3151
ref(const) or ref(param) where there is a small number of different
3152
values of param, then the access will likely hit the disk cache and will
3153
not require any disk seeks.
3155
The proper solution would be to assume an LRU disk cache of some size,
3156
calculate probability of cache hits, etc. For now we just count
3157
identical ref accesses as one.
3160
Expected number of row combinations
3162
static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref)
3165
optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3166
for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1);
3170
if (pos->examinePosition(found_ref))
3172
found_ref|= pos->getRefDependMap();
3174
For the case of "t1 LEFT Join t2 ON ..." where t2 is a const table
3175
with no matching row we will get position[t2].records_read==0.
3176
Actually the size of output is one null-complemented row, therefore
3177
we will use value of 1 whenever we get records_read==0.
3180
- the above case can't occur if inner part of outer join has more
3181
than one table: table with no matches will not be marked as const.
3183
- Ideally we should add 1 to records_read for every possible null-
3184
complemented row. We're not doing it because: 1. it will require
3185
non-trivial code and add overhead. 2. The value of records_read
3186
is an inprecise estimate and adding 1 (or, in the worst case,
3187
#max_nested_outer_joins=64-1) will not make it any more precise.
3189
if (pos->getFanout() > DBL_EPSILON)
3190
found*= pos->getFanout();
3197
Set up join struct according to best position.
3199
static bool get_best_combination(Join *join)
3202
table_map used_tables;
3203
JoinTable *join_tab,*j;
3204
optimizer::KeyUse *keyuse;
3205
uint32_t table_count;
3206
Session *session=join->session;
3207
optimizer::Position cur_pos;
3209
table_count=join->tables;
3210
if (!(join->join_tab=join_tab=
3211
(JoinTable*) session->alloc(sizeof(JoinTable)*table_count)))
3216
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
3217
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
3220
cur_pos= join->getPosFromOptimalPlan(tablenr);
3221
*j= *cur_pos.getJoinTable();
3222
form=join->table[tablenr]=j->table;
3223
used_tables|= form->map;
3224
form->reginfo.join_tab=j;
3225
if (!*j->on_expr_ref)
3226
form->reginfo.not_exists_optimize=0; // Only with LEFT Join
3227
if (j->type == AM_CONST)
3228
continue; // Handled in make_join_stat..
3233
if (j->type == AM_SYSTEM)
3235
if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
3238
if (tablenr != join->const_tables)
3241
else if (create_ref_for_key(join, j, keyuse, used_tables))
3242
return(true); // Something went wrong
3245
for (i=0 ; i < table_count ; i++)
3246
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
3247
update_depend_map(join);
3251
/** Save const tables first as used tables. */
3252
static void set_position(Join *join,
3255
optimizer::KeyUse *key)
3257
optimizer::Position tmp_pos(1.0, /* This is a const table */
3262
join->setPosInPartialPlan(idx, tmp_pos);
3264
/* Move the const table as down as possible in best_ref */
3265
JoinTable **pos=join->best_ref+idx+1;
3266
JoinTable *next=join->best_ref[idx];
3267
for (;next != table ; pos++)
3269
JoinTable *tmp=pos[0];
3273
join->best_ref[idx]=table;
3277
Selects and invokes a search strategy for an optimal query plan.
3279
The function checks user-configurable parameters that control the search
3280
strategy for an optimal plan, selects the search method and then invokes
3281
it. Each specific optimization procedure stores the final optimal plan in
3282
the array 'join->best_positions', and the cost of the plan in
3285
@param join pointer to the structure providing all context info for
3287
@param join_tables set of the tables in the query
3294
static bool choose_plan(Join *join, table_map join_tables)
3296
uint32_t search_depth= join->session->variables.optimizer_search_depth;
3297
uint32_t prune_level= join->session->variables.optimizer_prune_level;
3298
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
3300
join->cur_embedding_map.reset();
3301
reset_nj_counters(join->join_list);
3303
if (SELECT_STRAIGHT_JOIN option is set)
3304
reorder tables so dependent tables come after tables they depend
3305
on, otherwise keep tables in the order they were specified in the query
3307
Apply heuristic: pre-sort all access plans with respect to the number of
3310
internal::my_qsort(join->best_ref + join->const_tables,
3311
join->tables - join->const_tables, sizeof(JoinTable*),
3312
straight_join ? join_tab_cmp_straight : join_tab_cmp);
3315
optimize_straight_join(join, join_tables);
3319
if (search_depth == 0)
3320
/* Automatically determine a reasonable value for 'search_depth' */
3321
search_depth= determine_search_depth(join);
3322
if (greedy_search(join, join_tables, search_depth, prune_level))
3327
Store the cost of this query into a user variable
3328
Don't update last_query_cost for statements that are not "flat joins" :
3329
i.e. they have subqueries, unions or call stored procedures.
3330
TODO: calculate a correct cost for a query with subqueries and UNIONs.
3332
if (join->session->lex->is_single_level_stmt())
3333
join->session->status_var.last_query_cost= join->best_read;
3338
Find the best access path for an extension of a partial execution
3339
plan and add this path to the plan.
3341
The function finds the best access path to table 's' from the passed
3342
partial plan where an access path is the general term for any means to
3343
access the data in 's'. An access path may use either an index or a scan,
3344
whichever is cheaper. The input partial plan is passed via the array
3345
'join->positions' of length 'idx'. The chosen access method for 's' and its
3346
cost are stored in 'join->positions[idx]'.
3348
@param join pointer to the structure providing all context info
3350
@param s the table to be joined by the function
3351
@param session thread for the connection that submitted the query
3352
@param remaining_tables set of tables not included into the partial plan yet
3353
@param idx the length of the partial plan
3354
@param record_count estimate for the number of records returned by the
3356
@param read_time the cost of the partial plan
3361
static void best_access_path(Join *join,
3364
table_map remaining_tables,
3366
double record_count,
3369
optimizer::KeyUse *best_key= NULL;
3370
uint32_t best_max_key_part= 0;
3371
bool found_constraint= 0;
3372
double best= DBL_MAX;
3373
double best_time= DBL_MAX;
3374
double records= DBL_MAX;
3375
table_map best_ref_depends_map= 0;
3380
{ /* Use key if possible */
3381
Table *table= s->table;
3382
optimizer::KeyUse *keyuse= NULL;
3383
optimizer::KeyUse *start_key= NULL;
3384
double best_records= DBL_MAX;
3385
uint32_t max_key_part=0;
3387
/* Test how we can use keys */
3388
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
3389
for (keyuse= s->keyuse; keyuse->getTable() == table; )
3391
key_part_map found_part= 0;
3392
table_map found_ref= 0;
3393
uint32_t key= keyuse->getKey();
3394
KeyInfo *keyinfo= table->key_info + key;
3395
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
3396
key_part_map const_part= 0;
3397
/* The or-null keypart in ref-or-null access: */
3398
key_part_map ref_or_null_part= 0;
3400
/* Calculate how many key segments of the current key we can use */
3403
do /* For each keypart */
3405
uint32_t keypart= keyuse->getKeypart();
3406
table_map best_part_found_ref= 0;
3407
double best_prev_record_reads= DBL_MAX;
3409
do /* For each way to access the keypart */
3413
if 1. expression doesn't refer to forward tables
3414
2. we won't get two ref-or-null's
3416
if (! (remaining_tables & keyuse->getUsedTables()) &&
3417
! (ref_or_null_part && (keyuse->getOptimizeFlags() &
3418
KEY_OPTIMIZE_REF_OR_NULL)))
3420
found_part|= keyuse->getKeypartMap();
3421
if (! (keyuse->getUsedTables() & ~join->const_table_map))
3422
const_part|= keyuse->getKeypartMap();
3424
double tmp2= prev_record_reads(join, idx, (found_ref |
3425
keyuse->getUsedTables()));
3426
if (tmp2 < best_prev_record_reads)
3428
best_part_found_ref= keyuse->getUsedTables() & ~join->const_table_map;
3429
best_prev_record_reads= tmp2;
3431
if (rec > keyuse->getTableRows())
3432
rec= keyuse->getTableRows();
3434
If there is one 'key_column IS NULL' expression, we can
3435
use this ref_or_null optimisation of this field
3437
if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)
3438
ref_or_null_part|= keyuse->getKeypartMap();
3442
} while (keyuse->getTable() == table && keyuse->getKey() == key &&
3443
keyuse->getKeypart() == keypart);
3444
found_ref|= best_part_found_ref;
3445
} while (keyuse->getTable() == table && keyuse->getKey() == key);
3448
Assume that that each key matches a proportional part of table.
3451
continue; // Nothing usable found
3453
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
3454
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
3457
found_constraint= 1;
3460
Check if we found full key
3462
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
3465
max_key_part= UINT32_MAX;
3466
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
3468
tmp = prev_record_reads(join, idx, found_ref);
3474
{ /* We found a const key */
3476
ReuseRangeEstimateForRef-1:
3477
We get here if we've found a ref(const) (c_i are constants):
3478
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
3480
If range optimizer was able to construct a "range"
3481
access on this index, then its condition "quick_cond" was
3482
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
3483
from the range optimizer.
3485
Proof of (*): By properties of range and ref optimizers
3486
quick_cond will be equal or tighther than ref_const_cond.
3487
ref_const_cond already covers "smallest" possible interval -
3488
a singlepoint interval over all keyparts. Therefore,
3489
quick_cond is equivalent to ref_const_cond (if it was an
3490
empty interval we wouldn't have got here).
3492
if (table->quick_keys.test(key))
3493
records= (double) table->quick_rows[key];
3496
/* quick_range couldn't use key! */
3497
records= (double) s->records/rec;
3502
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
3503
{ /* Prefer longer keys */
3505
((double) s->records / (double) rec *
3507
((double) (table->getShare()->max_key_length-keyinfo->key_length) /
3508
(double) table->getShare()->max_key_length)));
3510
records=2.0; /* Can't be as good as a unique */
3513
ReuseRangeEstimateForRef-2: We get here if we could not reuse
3514
E(#rows) from range optimizer. Make another try:
3516
If range optimizer produced E(#rows) for a prefix of the ref
3517
access we're considering, and that E(#rows) is lower then our
3518
current estimate, make an adjustment. The criteria of when we
3519
can make an adjustment is a special case of the criteria used
3520
in ReuseRangeEstimateForRef-3.
3522
if (table->quick_keys.test(key) &&
3523
const_part & (1 << table->quick_key_parts[key]) &&
3524
table->quick_n_ranges[key] == 1 &&
3525
records > (double) table->quick_rows[key])
3527
records= (double) table->quick_rows[key];
3530
/* Limit the number of matched rows */
3532
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3533
if (table->covering_keys.test(key))
3535
/* we can use only index tree */
3536
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3539
tmp= record_count * min(tmp,s->worst_seeks);
3545
Use as much key-parts as possible and a uniq key is better
3546
than a not unique key
3547
Set tmp to (previous record count) * (records / combination)
3549
if ((found_part & 1) &&
3550
(!(table->index_flags(key) & HA_ONLY_WHOLE_INDEX) ||
3551
found_part == PREV_BITS(uint, keyinfo->key_parts)))
3553
max_key_part= max_part_bit(found_part);
3555
ReuseRangeEstimateForRef-3:
3556
We're now considering a ref[or_null] access via
3557
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
3558
(same-as-above but with one cond replaced
3559
with "t.keypart_i IS NULL")] (**)
3561
Try re-using E(#rows) from "range" optimizer:
3562
We can do so if "range" optimizer used the same intervals as
3563
in (**). The intervals used by range optimizer may be not
3564
available at this point (as "range" access might have choosen to
3565
create quick select over another index), so we can't compare
3566
them to (**). We'll make indirect judgements instead.
3567
The sufficient conditions for re-use are:
3568
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
3569
this is not satisfied we have no way to know which ranges
3570
will be actually scanned by 'ref' until we execute the
3572
(C2) max #key parts in 'range' access == K == max_key_part (this
3573
is apparently a necessary requirement)
3575
We also have a property that "range optimizer produces equal or
3576
tighter set of scan intervals than ref(const) optimizer". Each
3577
of the intervals in (**) are "tightest possible" intervals when
3578
one limits itself to using keyparts 1..K (which we do in #2).
3579
From here it follows that range access used either one, or
3580
both of the (I1) and (I2) intervals:
3582
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
3583
(same-as-above but with one cond replaced
3584
with "t.keypart_i IS NULL") (I2)
3586
The remaining part is to exclude the situation where range
3587
optimizer used one interval while we're considering
3588
ref-or-null and looking for estimate for two intervals. This
3589
is done by last limitation:
3591
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
3593
if (table->quick_keys.test(key) && !found_ref && //(C1)
3594
table->quick_key_parts[key] == max_key_part && //(C2)
3595
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
3597
tmp= records= (double) table->quick_rows[key];
3601
/* Check if we have statistic about the distribution */
3602
if ((records= keyinfo->rec_per_key[max_key_part-1]))
3605
Fix for the case where the index statistics is too
3607
(1) We're considering ref(const) and there is quick select
3609
(2) and that quick select uses more keyparts (i.e. it will
3610
scan equal/smaller interval then this ref(const))
3611
(3) and E(#rows) for quick select is higher then our
3614
We'll use E(#rows) from quick select.
3616
Q: Why do we choose to use 'ref'? Won't quick select be
3617
cheaper in some cases ?
3618
TODO: figure this out and adjust the plan choice if needed.
3620
if (!found_ref && table->quick_keys.test(key) && // (1)
3621
table->quick_key_parts[key] > max_key_part && // (2)
3622
records < (double)table->quick_rows[key]) // (3)
3623
records= (double)table->quick_rows[key];
3630
Assume that the first key part matches 1% of the cursor
3631
and that the whole key matches 10 (duplicates) or 1
3633
Assume also that more key matches proportionally more
3635
This gives the formula:
3636
records = (x * (b-a) + a*c-b)/(c-1)
3638
b = records matched by whole key
3639
a = records matched by first key part (1% of all records?)
3640
c = number of key parts in key
3641
x = used key parts (1 <= x <= c)
3644
if (!(rec_per_key=(double)
3645
keyinfo->rec_per_key[keyinfo->key_parts-1]))
3646
rec_per_key=(double) s->records/rec+1;
3650
else if (rec_per_key/(double) s->records >= 0.01)
3654
double a=s->records*0.01;
3655
if (keyinfo->key_parts > 1)
3656
tmp= (max_key_part * (rec_per_key - a) +
3657
a*keyinfo->key_parts - rec_per_key)/
3658
(keyinfo->key_parts-1);
3661
set_if_bigger(tmp,1.0);
3663
records = (uint32_t) tmp;
3666
if (ref_or_null_part)
3668
/* We need to do two key searches to find key */
3674
ReuseRangeEstimateForRef-4: We get here if we could not reuse
3675
E(#rows) from range optimizer. Make another try:
3677
If range optimizer produced E(#rows) for a prefix of the ref
3678
access we're considering, and that E(#rows) is lower then our
3679
current estimate, make the adjustment.
3681
The decision whether we can re-use the estimate from the range
3682
optimizer is the same as in ReuseRangeEstimateForRef-3,
3683
applied to first table->quick_key_parts[key] key parts.
3685
if (table->quick_keys.test(key) &&
3686
table->quick_key_parts[key] <= max_key_part &&
3687
const_part & (1 << table->quick_key_parts[key]) &&
3688
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
3689
const_part) ? 1 : 0) &&
3690
records > (double) table->quick_rows[key])
3692
tmp= records= (double) table->quick_rows[key];
3696
/* Limit the number of matched rows */
3697
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3698
if (table->covering_keys.test(key))
3700
/* we can use only index tree */
3701
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3704
tmp= record_count * min(tmp,s->worst_seeks);
3707
tmp= best_time; // Do nothing
3711
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
3713
best_time= tmp + records/(double) TIME_FOR_COMPARE;
3715
best_records= records;
3716
best_key= start_key;
3717
best_max_key_part= max_key_part;
3718
best_ref_depends_map= found_ref;
3721
records= best_records;
3725
Don't test table scan if it can't be better.
3726
Prefer key lookup if we would use the same key for scanning.
3728
Don't do a table scan on InnoDB tables, if we can read the used
3729
parts of the row from any of the used index.
3730
This is because table scans uses index and we would not win
3731
anything by using a table scan.
3733
A word for word translation of the below if-statement in sergefp's
3734
understanding: we check if we should use table scan if:
3735
(1) The found 'ref' access produces more records than a table scan
3736
(or index scan, or quick select), or 'ref' is more expensive than
3738
(2) This doesn't hold: the best way to perform table scan is to to perform
3739
'range' access using index IDX, and the best way to perform 'ref'
3740
access is to use the same index IDX, with the same or more key parts.
3741
(note: it is not clear how this rule is/should be extended to
3742
index_merge quick selects)
3743
(3) See above note about InnoDB.
3744
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
3745
path, but there is no quick select)
3746
If the condition in the above brackets holds, then the only possible
3747
"table scan" access method is ALL/index (there is no quick select).
3748
Since we have a 'ref' access path, and FORCE INDEX instructs us to
3749
choose it over ALL/index, there is no need to consider a full table
3752
if ((records >= s->found_records || best > s->read_time) && // (1)
3753
! (s->quick && best_key && s->quick->index == best_key->getKey() && // (2)
3754
best_max_key_part >= s->table->quick_key_parts[best_key->getKey()]) &&// (2)
3755
! ((s->table->cursor->getEngine()->check_flag(HTON_BIT_TABLE_SCAN_ON_INDEX)) && // (3)
3756
! s->table->covering_keys.none() && best_key && !s->quick) && // (3)
3757
! (s->table->force_index && best_key && !s->quick)) // (4)
3758
{ // Check full join
3759
ha_rows rnd_records= s->found_records;
3761
If there is a filtering condition on the table (i.e. ref analyzer found
3762
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
3763
preceding this table in the join order we're now considering), then
3764
assume that 25% of the rows will be filtered out by this condition.
3766
This heuristic is supposed to force tables used in exprZ to be before
3767
this table in join order.
3769
if (found_constraint)
3770
rnd_records-= rnd_records/4;
3773
If applicable, get a more accurate estimate. Don't use the two
3776
if (s->table->quick_condition_rows != s->found_records)
3777
rnd_records= s->table->quick_condition_rows;
3780
Range optimizer never proposes a RANGE if it isn't better
3781
than FULL: so if RANGE is present, it's always preferred to FULL.
3782
Here we estimate its cost.
3788
- read record range through 'quick'
3789
- skip rows which does not satisfy WHERE constraints
3791
We take into account possible use of join cache for ALL/index
3792
access (see first else-branch below), but we don't take it into
3793
account here for range/index_merge access. Find out why this is so.
3796
(s->quick->read_time +
3797
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
3801
/* Estimate cost of reading table. */
3802
tmp= s->table->cursor->scan_time();
3803
if (s->table->map & join->outer_join) // Can't use join cache
3806
For each record we have to:
3807
- read the whole table record
3808
- skip rows which does not satisfy join condition
3812
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
3816
/* We read the table as many times as join buffer becomes full. */
3817
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
3819
(double) session->variables.join_buff_size));
3821
We don't make full cartesian product between rows in the scanned
3822
table and existing records because we skip all rows from the
3823
scanned table, which does not satisfy join condition when
3824
we read the table (see flush_cached_records for details). Here we
3825
take into account cost to read and skip these records.
3827
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
3832
We estimate the cost of evaluating WHERE clause for found records
3833
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
3834
tmp give us total cost of using Table SCAN
3836
if (best == DBL_MAX ||
3837
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
3838
best + record_count/(double) TIME_FOR_COMPARE*records))
3841
If the table has a range (s->quick is set) make_join_select()
3842
will ensure that this will be used
3845
records= rows2double(rnd_records);
3847
/* range/index_merge/ALL/index access method are "independent", so: */
3848
best_ref_depends_map= 0;
3852
/* Update the cost information for the current partial plan */
3853
optimizer::Position tmp_pos(records,
3857
best_ref_depends_map);
3858
join->setPosInPartialPlan(idx, tmp_pos);
3861
idx == join->const_tables &&
3862
s->table == join->sort_by_table &&
3863
join->unit->select_limit_cnt >= records)
3864
join->sort_by_table= (Table*) 1; // Must use temporary table
3870
Select the best ways to access the tables in a query without reordering them.
3872
Find the best access paths for each query table and compute their costs
3873
according to their order in the array 'join->best_ref' (thus without
3874
reordering the join tables). The function calls sequentially
3875
'best_access_path' for each table in the query to select the best table
3876
access method. The final optimal plan is stored in the array
3877
'join->best_positions', and the corresponding cost in 'join->best_read'.
3879
@param join pointer to the structure providing all context info for
3881
@param join_tables set of the tables in the query
3884
This function can be applied to:
3885
- queries with STRAIGHT_JOIN
3886
- internally to compute the cost of an arbitrary QEP
3888
Thus 'optimize_straight_join' can be used at any stage of the query
3889
optimization process to finalize a QEP as it is.
3891
static void optimize_straight_join(Join *join, table_map join_tables)
3894
optimizer::Position partial_pos;
3895
uint32_t idx= join->const_tables;
3896
double record_count= 1.0;
3897
double read_time= 0.0;
3899
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
3901
/* Find the best access method from 's' to the current partial plan */
3902
best_access_path(join, s, join->session, join_tables, idx,
3903
record_count, read_time);
3904
/* compute the cost of the new plan extended with 's' */
3905
partial_pos= join->getPosFromPartialPlan(idx);
3906
record_count*= partial_pos.getFanout();
3907
read_time+= partial_pos.getCost();
3908
join_tables&= ~(s->table->map);
3912
read_time+= record_count / (double) TIME_FOR_COMPARE;
3913
partial_pos= join->getPosFromPartialPlan(join->const_tables);
3914
if (join->sort_by_table &&
3915
partial_pos.hasTableForSorting(join->sort_by_table))
3916
read_time+= record_count; // We have to make a temp table
3917
join->copyPartialPlanIntoOptimalPlan(idx);
3918
join->best_read= read_time;
3922
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
3924
The search procedure uses a hybrid greedy/exhaustive search with controlled
3925
exhaustiveness. The search is performed in N = card(remaining_tables)
3926
steps. Each step evaluates how promising is each of the unoptimized tables,
3927
selects the most promising table, and extends the current partial QEP with
3928
that table. Currenly the most 'promising' table is the one with least
3929
expensive extension.\
3931
There are two extreme cases:
3932
-# When (card(remaining_tables) < search_depth), the estimate finds the
3933
best complete continuation of the partial QEP. This continuation can be
3934
used directly as a result of the search.
3935
-# When (search_depth == 1) the 'best_extension_by_limited_search'
3936
consideres the extension of the current QEP with each of the remaining
3939
All other cases are in-between these two extremes. Thus the parameter
3940
'search_depth' controlls the exhaustiveness of the search. The higher the
3941
value, the longer the optimizaton time and possibly the better the
3942
resulting plan. The lower the value, the fewer alternative plans are
3943
estimated, but the more likely to get a bad QEP.
3945
All intermediate and final results of the procedure are stored in 'join':
3946
- join->positions : modified for every partial QEP that is explored
3947
- join->best_positions: modified for the current best complete QEP
3948
- join->best_read : modified for the current best complete QEP
3949
- join->best_ref : might be partially reordered
3951
The final optimal plan is stored in 'join->best_positions', and its
3952
corresponding cost in 'join->best_read'.
3955
The following pseudocode describes the algorithm of 'greedy_search':
3958
procedure greedy_search
3959
input: remaining_tables
3964
(t, a) = best_extension(pplan, remaining_tables);
3965
pplan = concat(pplan, (t, a));
3966
remaining_tables = remaining_tables - t;
3967
} while (remaining_tables != {})
3972
where 'best_extension' is a placeholder for a procedure that selects the
3973
most "promising" of all tables in 'remaining_tables'.
3974
Currently this estimate is performed by calling
3975
'best_extension_by_limited_search' to evaluate all extensions of the
3976
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
3977
mainly depends on that of 'best_extension_by_limited_search'.
3980
If 'best_extension()' == 'best_extension_by_limited_search()', then the
3981
worst-case complexity of this algorithm is <=
3982
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
3983
complexity of greedy_search is O(N!).
3986
In the future, 'greedy_search' might be extended to support other
3987
implementations of 'best_extension', e.g. some simpler quadratic procedure.
3989
@param join pointer to the structure providing all context info
3991
@param remaining_tables set of tables not included into the partial plan yet
3992
@param search_depth controlls the exhaustiveness of the search
3993
@param prune_level the pruning heuristics that should be applied during
4001
static bool greedy_search(Join *join,
4002
table_map remaining_tables,
4003
uint32_t search_depth,
4004
uint32_t prune_level)
4006
double record_count= 1.0;
4007
double read_time= 0.0;
4008
uint32_t idx= join->const_tables; // index into 'join->best_ref'
4010
uint32_t size_remain; // cardinality of remaining_tables
4011
optimizer::Position best_pos;
4012
JoinTable *best_table; // the next plan node to be added to the curr QEP
4014
/* number of tables that remain to be optimized */
4015
size_remain= internal::my_count_bits(remaining_tables);
4018
/* Find the extension of the current QEP with the lowest cost */
4019
join->best_read= DBL_MAX;
4020
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
4021
read_time, search_depth, prune_level))
4024
if (size_remain <= search_depth)
4027
'join->best_positions' contains a complete optimal extension of the
4028
current partial QEP.
4033
/* select the first table in the optimal extension as most promising */
4034
best_pos= join->getPosFromOptimalPlan(idx);
4035
best_table= best_pos.getJoinTable();
4037
Each subsequent loop of 'best_extension_by_limited_search' uses
4038
'join->positions' for cost estimates, therefore we have to update its
4041
join->setPosInPartialPlan(idx, best_pos);
4044
We need to make best_extension_by_limited_search aware of the fact
4045
that it's not starting from top level, but from a rather specific
4046
position in the list of nested joins.
4048
check_interleaving_with_nj (best_table);
4052
/* find the position of 'best_table' in 'join->best_ref' */
4054
JoinTable *pos= join->best_ref[best_idx];
4055
while (pos && best_table != pos)
4056
pos= join->best_ref[++best_idx];
4057
assert((pos != NULL)); // should always find 'best_table'
4058
/* move 'best_table' at the first free position in the array of joins */
4059
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
4061
/* compute the cost of the new plan extended with 'best_table' */
4062
optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
4063
record_count*= partial_pos.getFanout();
4064
read_time+= partial_pos.getCost();
4066
remaining_tables&= ~(best_table->table->map);
4074
Find a good, possibly optimal, query execution plan (QEP) by a possibly
4077
The procedure searches for the optimal ordering of the query tables in set
4078
'remaining_tables' of size N, and the corresponding optimal access paths to
4079
each table. The choice of a table order and an access path for each table
4080
constitutes a query execution plan (QEP) that fully specifies how to
4083
The maximal size of the found plan is controlled by the parameter
4084
'search_depth'. When search_depth == N, the resulting plan is complete and
4085
can be used directly as a QEP. If search_depth < N, the found plan consists
4086
of only some of the query tables. Such "partial" optimal plans are useful
4087
only as input to query optimization procedures, and cannot be used directly
4090
The algorithm begins with an empty partial plan stored in 'join->positions'
4091
and a set of N tables - 'remaining_tables'. Each step of the algorithm
4092
evaluates the cost of the partial plan extended by all access plans for
4093
each of the relations in 'remaining_tables', expands the current partial
4094
plan with the access plan that results in lowest cost of the expanded
4095
partial plan, and removes the corresponding relation from
4096
'remaining_tables'. The algorithm continues until it either constructs a
4097
complete optimal plan, or constructs an optimal plartial plan with size =
4100
The final optimal plan is stored in 'join->best_positions'. The
4101
corresponding cost of the optimal plan is in 'join->best_read'.
4104
The procedure uses a recursive depth-first search where the depth of the
4105
recursion (and thus the exhaustiveness of the search) is controlled by the
4106
parameter 'search_depth'.
4109
The pseudocode below describes the algorithm of
4110
'best_extension_by_limited_search'. The worst-case complexity of this
4111
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
4112
the complexity of greedy_search is O(N!).
4115
procedure best_extension_by_limited_search(
4116
pplan in, // in, partial plan of tables-joined-so-far
4117
pplan_cost, // in, cost of pplan
4118
remaining_tables, // in, set of tables not referenced in pplan
4119
best_plan_so_far, // in/out, best plan found so far
4120
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
4121
search_depth) // in, maximum size of the plans being considered
4123
for each table T from remaining_tables
4125
// Calculate the cost of using table T as above
4126
cost = complex-series-of-calculations;
4128
// Add the cost to the cost so far.
4131
if (pplan_cost >= best_plan_so_far_cost)
4132
// pplan_cost already too great, stop search
4135
pplan= expand pplan by best_access_method;
4136
remaining_tables= remaining_tables - table T;
4137
if (remaining_tables is not an empty set
4141
best_extension_by_limited_search(pplan, pplan_cost,
4144
best_plan_so_far_cost,
4149
best_plan_so_far_cost= pplan_cost;
4150
best_plan_so_far= pplan;
4157
When 'best_extension_by_limited_search' is called for the first time,
4158
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
4159
The actual implementation provides a way to optionally use pruning
4160
heuristic (controlled by the parameter 'prune_level') to reduce the search
4161
space by skipping some partial plans.
4164
The parameter 'search_depth' provides control over the recursion
4165
depth, and thus the size of the resulting optimal plan.
4167
@param join pointer to the structure providing all context info
4169
@param remaining_tables set of tables not included into the partial plan yet
4170
@param idx length of the partial QEP in 'join->positions';
4171
since a depth-first search is used, also corresponds
4172
to the current depth of the search tree;
4173
also an index in the array 'join->best_ref';
4174
@param record_count estimate for the number of records returned by the
4176
@param read_time the cost of the best partial plan
4177
@param search_depth maximum depth of the recursion and thus size of the
4179
(0 < search_depth <= join->tables+1).
4180
@param prune_level pruning heuristics that should be applied during
4182
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
4189
static bool best_extension_by_limited_search(Join *join,
4190
table_map remaining_tables,
4192
double record_count,
4194
uint32_t search_depth,
4195
uint32_t prune_level)
4197
Session *session= join->session;
4198
if (session->killed) // Abort
4202
'join' is a partial plan with lower cost than the best plan so far,
4203
so continue expanding it further with the tables in 'remaining_tables'.
4206
double best_record_count= DBL_MAX;
4207
double best_read_time= DBL_MAX;
4208
optimizer::Position partial_pos;
4210
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4212
table_map real_table_bit= s->table->map;
4213
if ((remaining_tables & real_table_bit) &&
4214
! (remaining_tables & s->dependent) &&
4215
(! idx || ! check_interleaving_with_nj(s)))
4217
double current_record_count, current_read_time;
4220
psergey-insideout-todo:
4221
when best_access_path() detects it could do an InsideOut scan or
4222
some other scan, have it return an insideout scan and a flag that
4223
requests to "fork" this loop iteration. (Q: how does that behave
4224
when the depth is insufficient??)
4226
/* Find the best access method from 's' to the current partial plan */
4227
best_access_path(join, s, session, remaining_tables, idx,
4228
record_count, read_time);
4229
/* Compute the cost of extending the plan with 's' */
4230
partial_pos= join->getPosFromPartialPlan(idx);
4231
current_record_count= record_count * partial_pos.getFanout();
4232
current_read_time= read_time + partial_pos.getCost();
4234
/* Expand only partial plans with lower cost than the best QEP so far */
4235
if ((current_read_time +
4236
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
4238
restore_prev_nj_state(s);
4243
Prune some less promising partial plans. This heuristic may miss
4244
the optimal QEPs, thus it results in a non-exhaustive search.
4246
if (prune_level == 1)
4248
if (best_record_count > current_record_count ||
4249
best_read_time > current_read_time ||
4250
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
4252
if (best_record_count >= current_record_count &&
4253
best_read_time >= current_read_time &&
4254
/* TODO: What is the reasoning behind this condition? */
4255
(! (s->key_dependent & remaining_tables) ||
4256
partial_pos.isConstTable()))
4258
best_record_count= current_record_count;
4259
best_read_time= current_read_time;
4264
restore_prev_nj_state(s);
4269
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
4270
{ /* Recursively expand the current partial plan */
4271
std::swap(join->best_ref[idx], *pos);
4272
if (best_extension_by_limited_search(join,
4273
remaining_tables & ~real_table_bit,
4275
current_record_count,
4280
std::swap(join->best_ref[idx], *pos);
4284
'join' is either the best partial QEP with 'search_depth' relations,
4285
or the best complete QEP so far, whichever is smaller.
4287
partial_pos= join->getPosFromPartialPlan(join->const_tables);
4288
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4289
if (join->sort_by_table &&
4290
partial_pos.hasTableForSorting(join->sort_by_table))
4291
/* We have to make a temp table */
4292
current_read_time+= current_record_count;
4293
if ((search_depth == 1) || (current_read_time < join->best_read))
4295
join->copyPartialPlanIntoOptimalPlan(idx + 1);
4296
join->best_read= current_read_time - 0.001;
4299
restore_prev_nj_state(s);
4306
Heuristic procedure to automatically guess a reasonable degree of
4307
exhaustiveness for the greedy search procedure.
4309
The procedure estimates the optimization time and selects a search depth
4310
big enough to result in a near-optimal QEP, that doesn't take too long to
4311
find. If the number of tables in the query exceeds some constant, then
4312
search_depth is set to this constant.
4314
@param join pointer to the structure providing all context info for
4318
This is an extremely simplistic implementation that serves as a stub for a
4319
more advanced analysis of the join. Ideally the search depth should be
4320
determined by learning from previous query optimizations, because it will
4321
depend on the CPU power (and other factors).
4324
this value should be determined dynamically, based on statistics:
4325
uint32_t max_tables_for_exhaustive_opt= 7;
4328
this value could be determined by some mapping of the form:
4329
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4332
A positive integer that specifies the search depth (and thus the
4333
exhaustiveness) of the depth-first search algorithm used by
4336
static uint32_t determine_search_depth(Join *join)
4338
uint32_t table_count= join->tables - join->const_tables;
4339
uint32_t search_depth;
4340
/* TODO: this value should be determined dynamically, based on statistics: */
4341
uint32_t max_tables_for_exhaustive_opt= 7;
4343
if (table_count <= max_tables_for_exhaustive_opt)
4344
search_depth= table_count+1; // use exhaustive for small number of tables
4347
TODO: this value could be determined by some mapping of the form:
4348
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4350
search_depth= max_tables_for_exhaustive_opt; // use greedy search
4352
return search_depth;
4355
static bool make_simple_join(Join *join,Table *tmp_table)
4358
JoinTable *join_tab;
4361
Reuse Table * and JoinTable if already allocated by a previous call
4362
to this function through Join::exec (may happen for sub-queries).
4364
if (!join->table_reexec)
4366
if (!(join->table_reexec= (Table**) join->session->alloc(sizeof(Table*))))
4369
join->tmp_join->table_reexec= join->table_reexec;
4371
if (!join->join_tab_reexec)
4373
if (!(join->join_tab_reexec=
4374
(JoinTable*) join->session->alloc(sizeof(JoinTable))))
4377
join->tmp_join->join_tab_reexec= join->join_tab_reexec;
4379
tableptr= join->table_reexec;
4380
join_tab= join->join_tab_reexec;
4382
join->join_tab=join_tab;
4383
join->table=tableptr; tableptr[0]=tmp_table;
4385
join->const_tables=0;
4386
join->const_table_map=0;
4387
join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=
4388
join->tmp_table_param.func_count=0;
4389
join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;
4390
join->first_record=join->sort_and_group=0;
4391
join->send_records=(ha_rows) 0;
4393
join->row_limit=join->unit->select_limit_cnt;
4394
join->do_send_rows = (join->row_limit) ? 1 : 0;
4396
join_tab->cache.buff=0; /* No caching */
4397
join_tab->table=tmp_table;
4399
join_tab->select_cond=0;
4401
join_tab->type= AM_ALL; /* Map through all records */
4402
join_tab->keys.set(); /* test everything in quick */
4404
join_tab->on_expr_ref=0;
4405
join_tab->last_inner= 0;
4406
join_tab->first_unmatched= 0;
4407
join_tab->ref.key = -1;
4408
join_tab->not_used_in_distinct=0;
4409
join_tab->read_first_record= join_init_read_record;
4410
join_tab->join=join;
4411
join_tab->ref.key_parts= 0;
4412
join_tab->read_record.init();
4413
tmp_table->status=0;
4414
tmp_table->null_row=0;
4420
Fill in outer join related info for the execution plan structure.
4422
For each outer join operation left after simplification of the
4423
original query the function set up the following pointers in the linear
4424
structure join->join_tab representing the selected execution plan.
4425
The first inner table t0 for the operation is set to refer to the last
4426
inner table tk through the field t0->last_inner.
4427
Any inner table ti for the operation are set to refer to the first
4428
inner table ti->first_inner.
4429
The first inner table t0 for the operation is set to refer to the
4430
first inner table of the embedding outer join operation, if there is any,
4431
through the field t0->first_upper.
4432
The on expression for the outer join operation is attached to the
4433
corresponding first inner table through the field t0->on_expr_ref.
4434
Here ti are structures of the JoinTable type.
4436
EXAMPLE. For the query:
4440
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
4441
ON (t1.a=t2.a AND t1.b=t3.b)
4445
given the execution plan with the table order t1,t2,t3,t4
4446
is selected, the following references will be set;
4447
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
4448
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
4449
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
4450
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
4452
@param join reference to the info fully describing the query
4455
The function assumes that the simplification procedure has been
4456
already applied to the join query (see simplify_joins).
4457
This function can be called only after the execution plan
4460
static void make_outerjoin_info(Join *join)
4462
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4464
JoinTable *tab=join->join_tab+i;
4465
Table *table=tab->table;
4466
TableList *tbl= table->pos_in_table_list;
4467
TableList *embedding= tbl->getEmbedding();
4469
if (tbl->outer_join)
4472
Table tab is the only one inner table for outer join.
4473
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
4474
is in the query above.)
4476
tab->last_inner= tab->first_inner= tab;
4477
tab->on_expr_ref= &tbl->on_expr;
4478
tab->cond_equal= tbl->cond_equal;
4480
tab->first_upper= embedding->getNestedJoin()->first_nested;
4482
for ( ; embedding ; embedding= embedding->getEmbedding())
4484
/* Ignore sj-nests: */
4485
if (!embedding->on_expr)
4487
nested_join_st *nested_join= embedding->getNestedJoin();
4488
if (!nested_join->counter_)
4491
Table tab is the first inner table for nested_join.
4492
Save reference to it in the nested join structure.
4494
nested_join->first_nested= tab;
4495
tab->on_expr_ref= &embedding->on_expr;
4496
tab->cond_equal= tbl->cond_equal;
4497
if (embedding->getEmbedding())
4498
tab->first_upper= embedding->getEmbedding()->getNestedJoin()->first_nested;
4500
if (!tab->first_inner)
4501
tab->first_inner= nested_join->first_nested;
4502
if (++nested_join->counter_ < nested_join->join_list.elements)
4504
/* Table tab is the last inner table for nested join. */
4505
nested_join->first_nested->last_inner= tab;
4511
static bool make_join_select(Join *join,
4512
optimizer::SqlSelect *select,
4515
Session *session= join->session;
4516
optimizer::Position cur_pos;
4519
add_not_null_conds(join);
4520
table_map used_tables;
4521
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
4522
{ /* there may be a select without a cond. */
4523
if (join->tables > 1)
4524
cond->update_used_tables(); // Tablenr may have changed
4525
if (join->const_tables == join->tables &&
4526
session->lex->current_select->master_unit() ==
4527
&session->lex->unit) // not upper level SELECT
4528
join->const_table_map|=RAND_TABLE_BIT;
4529
{ // Check const tables
4531
make_cond_for_table(cond,
4532
join->const_table_map,
4534
for (JoinTable *tab= join->join_tab+join->const_tables;
4535
tab < join->join_tab+join->tables ; tab++)
4537
if (*tab->on_expr_ref)
4539
JoinTable *cond_tab= tab->first_inner;
4540
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
4541
join->const_table_map,
4545
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4548
tmp->quick_fix_field();
4549
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4550
new Item_cond_and(cond_tab->select_cond,
4552
if (! cond_tab->select_cond)
4554
cond_tab->select_cond->quick_fix_field();
4557
if (const_cond && ! const_cond->val_int())
4559
return 1; // Impossible const condition
4563
used_tables=((select->const_tables=join->const_table_map) |
4564
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4565
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4567
JoinTable *tab=join->join_tab+i;
4569
first_inner is the X in queries like:
4570
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
4572
JoinTable *first_inner_tab= tab->first_inner;
4573
table_map current_map= tab->table->map;
4574
bool use_quick_range=0;
4578
Following force including random expression in last table condition.
4579
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
4581
if (i == join->tables-1)
4582
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
4583
used_tables|=current_map;
4585
if (tab->type == AM_REF && tab->quick &&
4586
(uint32_t) tab->ref.key == tab->quick->index &&
4587
tab->ref.key_length < tab->quick->max_used_key_length)
4589
/* Range uses longer key; Use this instead of ref on key */
4594
tab->ref.key_parts= 0; // Don't use ref key.
4595
cur_pos= join->getPosFromOptimalPlan(i);
4596
cur_pos.setFanout(rows2double(tab->quick->records));
4598
We will use join cache here : prevent sorting of the first
4599
table only and sort at the end.
4601
if (i != join->const_tables && join->tables > join->const_tables + 1)
4607
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
4608
if (cond && !tmp && tab->quick)
4610
if (tab->type != AM_ALL)
4613
Don't use the quick method
4614
We come here in the case where we have 'key=constant' and
4615
the test is removed by make_cond_for_table()
4623
Hack to handle the case where we only refer to a table
4624
in the ON part of an OUTER JOIN. In this case we want the code
4625
below to check if we should use 'quick' instead.
4627
tmp= new Item_int((int64_t) 1,1); // Always true
4631
if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||
4632
tab->type == AM_EQ_REF)
4634
optimizer::SqlSelect *sel= tab->select= ((optimizer::SqlSelect*)
4635
session->memdup((unsigned char*) select,
4638
return 1; // End of memory
4640
If tab is an inner table of an outer join operation,
4641
add a match guard to the pushed down predicate.
4642
The guard will turn the predicate on only after
4643
the first match for outer tables is encountered.
4648
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
4649
a cond, so neutralize the hack above.
4651
if (! (tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
4653
tab->select_cond=sel->cond=tmp;
4656
tab->select_cond= sel->cond= NULL;
4658
sel->head=tab->table;
4661
/* Use quick key read if it's a constant and it's not used
4663
if (tab->needed_reg.none() && tab->type != AM_EQ_REF
4664
&& (tab->type != AM_REF || (uint32_t) tab->ref.key == tab->quick->index))
4666
sel->quick=tab->quick; // Use value from get_quick_...
4667
sel->quick_keys.reset();
4668
sel->needed_reg.reset();
4676
uint32_t ref_key= static_cast<uint32_t>(sel->head->reginfo.join_tab->ref.key + 1);
4677
if (i == join->const_tables && ref_key)
4679
if (tab->const_keys.any() &&
4680
tab->table->reginfo.impossible_range)
4683
else if (tab->type == AM_ALL && ! use_quick_range)
4685
if (tab->const_keys.any() &&
4686
tab->table->reginfo.impossible_range)
4687
return 1; // Impossible range
4689
We plan to scan all rows.
4690
Check again if we should use an index.
4691
We could have used an column from a previous table in
4692
the index if we are using limit and this is the first table
4695
cur_pos= join->getPosFromOptimalPlan(i);
4696
if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
4697
(! tab->const_keys.none() && (i == join->const_tables) &&
4698
(join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4700
/* Join with outer join condition */
4701
COND *orig_cond= sel->cond;
4702
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
4705
We can't call sel->cond->fix_fields,
4706
as it will break tab->on_expr if it's AND condition
4707
(fix_fields currently removes extra AND/OR levels).
4708
Yet attributes of the just built condition are not needed.
4709
Thus we call sel->cond->quick_fix_field for safety.
4711
if (sel->cond && ! sel->cond->fixed)
4712
sel->cond->quick_fix_field();
4714
if (sel->test_quick_select(session, tab->keys,
4715
used_tables & ~ current_map,
4716
(join->select_options &
4719
join->unit->select_limit_cnt), 0,
4723
Before reporting "Impossible WHERE" for the whole query
4724
we have to check isn't it only "impossible ON" instead
4726
sel->cond=orig_cond;
4727
if (! *tab->on_expr_ref ||
4728
sel->test_quick_select(session, tab->keys,
4729
used_tables & ~ current_map,
4730
(join->select_options &
4733
join->unit->select_limit_cnt),0,
4735
return 1; // Impossible WHERE
4738
sel->cond=orig_cond;
4740
/* Fix for EXPLAIN */
4743
cur_pos= join->getPosFromOptimalPlan(i);
4744
cur_pos.setFanout(static_cast<double>(sel->quick->records));
4749
sel->needed_reg= tab->needed_reg;
4750
sel->quick_keys.reset();
4752
if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
4753
!((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
4755
tab->keys= sel->quick_keys;
4756
tab->keys|= sel->needed_reg;
4757
tab->use_quick= (!sel->needed_reg.none() &&
4758
(select->quick_keys.none() ||
4760
(select->quick->records >= 100L)))) ?
4762
sel->read_tables= used_tables & ~current_map;
4764
if (i != join->const_tables && tab->use_quick != 2)
4765
{ /* Read with cache */
4767
(tmp=make_cond_for_table(cond,
4768
join->const_table_map |
4772
tab->cache.select= (optimizer::SqlSelect*)
4773
session->memdup((unsigned char*) sel, sizeof(optimizer::SqlSelect));
4774
tab->cache.select->cond= tmp;
4775
tab->cache.select->read_tables= join->const_table_map;
4782
Push down conditions from all on expressions.
4783
Each of these conditions are guarded by a variable
4784
that turns if off just before null complemented row for
4785
outer joins is formed. Thus, the condition from an
4786
'on expression' are guaranteed not to be checked for
4787
the null complemented row.
4790
/* First push down constant conditions from on expressions */
4791
for (JoinTable *join_tab= join->join_tab+join->const_tables;
4792
join_tab < join->join_tab+join->tables ; join_tab++)
4794
if (*join_tab->on_expr_ref)
4796
JoinTable *cond_tab= join_tab->first_inner;
4797
tmp= make_cond_for_table(*join_tab->on_expr_ref,
4798
join->const_table_map,
4802
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4805
tmp->quick_fix_field();
4806
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4807
new Item_cond_and(cond_tab->select_cond,tmp);
4808
if (! cond_tab->select_cond)
4810
cond_tab->select_cond->quick_fix_field();
4814
/* Push down non-constant conditions from on expressions */
4815
JoinTable *last_tab= tab;
4816
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
4819
Table tab is the last inner table of an outer join.
4820
An on expression is always attached to it.
4822
COND *on_expr= *first_inner_tab->on_expr_ref;
4824
table_map used_tables2= (join->const_table_map |
4825
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4826
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
4828
current_map= tab->table->map;
4829
used_tables2|= current_map;
4830
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
4834
JoinTable *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
4836
First add the guards for match variables of
4837
all embedding outer join operations.
4839
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
4844
Now add the guard turning the predicate off for
4845
the null complemented row.
4847
tmp_cond= new Item_func_trig_cond(tmp_cond,
4851
tmp_cond->quick_fix_field();
4852
/* Add the predicate to other pushed down predicates */
4853
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
4854
new Item_cond_and(cond_tab->select_cond,
4856
if (! cond_tab->select_cond)
4858
cond_tab->select_cond->quick_fix_field();
4861
first_inner_tab= first_inner_tab->first_upper;
4869
Plan refinement stage: do various set ups for the executioner
4872
make_join_readinfo()
4873
join Join being processed
4874
options Join's options (checking for SELECT_DESCRIBE,
4875
SELECT_NO_JOIN_CACHE)
4876
no_jbuf_after Don't use join buffering after table with this number.
4879
Plan refinement stage: do various set ups for the executioner
4880
- set up use of join buffering
4881
- push index conditions
4882
- increment counters
4887
true - Out of memory
4889
static bool make_join_readinfo(Join *join)
4893
for (uint32_t i= join->const_tables ; i < join->tables ; i++)
4895
JoinTable *tab=join->join_tab+i;
4896
Table *table=tab->table;
4897
tab->read_record.table= table;
4898
tab->read_record.cursor= table->cursor;
4899
tab->next_select=sub_select; /* normal select */
4901
TODO: don't always instruct first table's ref/range access method to
4902
produce sorted output.
4904
tab->sorted= sorted;
4905
sorted= false; // only first must be sorted
4907
if (tab->insideout_match_tab)
4909
if (! (tab->insideout_buf= (unsigned char*) join->session->alloc(tab->table->key_info
4915
optimizer::AccessMethodFactory &factory= optimizer::AccessMethodFactory::singleton();
4916
boost::shared_ptr<optimizer::AccessMethod> access_method(factory.createAccessMethod(tab->type));
4918
if (! access_method)
4922
* Is abort() the correct thing to call here? I call this here because it was what was called in
4923
* the default case for the switch statement that used to be here.
4928
access_method->getStats(table, tab);
4931
join->join_tab[join->tables-1].next_select= NULL; /* Set by do_select */
4936
/** Update the dependency map for the tables. */
4937
static void update_depend_map(Join *join)
4939
JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
4941
for (; join_tab != end ; join_tab++)
4943
table_reference_st *ref= &join_tab->ref;
4944
table_map depend_map= 0;
4945
Item **item=ref->items;
4947
for (i=0 ; i < ref->key_parts ; i++,item++)
4948
depend_map|=(*item)->used_tables();
4949
ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;
4950
depend_map&= ~OUTER_REF_TABLE_BIT;
4951
for (JoinTable **tab=join->map2table; depend_map; tab++,depend_map>>=1 )
4954
ref->depend_map|=(*tab)->ref.depend_map;
4959
/** Update the dependency map for the sort order. */
4960
static void update_depend_map(Join *join, order_st *order)
4962
for (; order ; order=order->next)
4964
table_map depend_map;
4965
order->item[0]->update_used_tables();
4966
order->depend_map=depend_map=order->item[0]->used_tables();
4967
// Not item_sum(), RAND() and no reference to table outside of sub select
4968
if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))
4969
&& !order->item[0]->with_sum_func)
4971
for (JoinTable **tab=join->map2table; depend_map; tab++, depend_map>>=1)
4974
order->depend_map|=(*tab)->ref.depend_map;
4981
Remove all constants and check if order_st only contains simple
4984
simple_order is set to 1 if sort_order only uses fields from head table
4985
and the head table is not a LEFT JOIN table.
4987
@param join Join handler
4988
@param first_order List of SORT or GROUP order
4989
@param cond WHERE statement
4990
@param change_list Set to 1 if we should remove things from list.
4991
If this is not set, then only simple_order is
4993
@param simple_order Set to 1 if we are only using simple expressions
4996
Returns new sort order
4998
static order_st *remove_constants(Join *join,order_st *first_order, COND *cond, bool change_list, bool *simple_order)
5000
if (join->tables == join->const_tables)
5001
return change_list ? 0 : first_order; // No need to sort
5003
order_st *order,**prev_ptr;
5004
table_map first_table= join->join_tab[join->const_tables].table->map;
5005
table_map not_const_tables= ~join->const_table_map;
5008
prev_ptr= &first_order;
5009
*simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;
5011
/* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
5013
update_depend_map(join, first_order);
5014
for (order=first_order; order ; order=order->next)
5016
table_map order_tables=order->item[0]->used_tables();
5017
if (order->item[0]->with_sum_func)
5018
*simple_order=0; // Must do a temp table to sort
5019
else if (!(order_tables & not_const_tables))
5021
if (order->item[0]->with_subselect)
5022
order->item[0]->val_str(&order->item[0]->str_value);
5023
continue; // skip const item
5027
if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))
5032
if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
5036
if ((ref=order_tables & (not_const_tables ^ first_table)))
5038
if (!(order_tables & first_table) &&
5039
only_eq_ref_tables(join,first_order, ref))
5043
*simple_order=0; // Must do a temp table to sort
5048
*prev_ptr= order; // use this entry
5049
prev_ptr= &order->next;
5053
if (prev_ptr == &first_order) // Nothing to sort/group
5055
return(first_order);
5058
static int return_zero_rows(Join *join,
5059
select_result *result,
5063
uint64_t select_options,
5067
if (select_options & SELECT_DESCRIBE)
5069
optimizer::ExplainPlan planner(join,
5074
planner.printPlan();
5082
for (TableList *table= tables; table; table= table->next_leaf)
5083
table->table->mark_as_null_row(); // All fields are NULL
5084
if (having && having->val_int() == 0)
5087
if (! (result->send_fields(fields)))
5091
List_iterator_fast<Item> it(fields);
5093
while ((item= it++))
5094
item->no_rows_in_result();
5095
result->send_data(fields);
5097
result->send_eof(); // Should be safe
5099
/* Update results for FOUND_ROWS */
5100
join->session->limit_found_rows= join->session->examined_row_count= 0;
5105
Simplify joins replacing outer joins by inner joins whenever it's
5108
The function, during a retrieval of join_list, eliminates those
5109
outer joins that can be converted into inner join, possibly nested.
5110
It also moves the on expressions for the converted outer joins
5111
and from inner joins to conds.
5112
The function also calculates some attributes for nested joins:
5116
- on_expr_dep_tables
5117
The first two attributes are used to test whether an outer join can
5118
be substituted for an inner join. The third attribute represents the
5119
relation 'to be dependent on' for tables. If table t2 is dependent
5120
on table t1, then in any evaluated execution plan table access to
5121
table t2 must precede access to table t2. This relation is used also
5122
to check whether the query contains invalid cross-references.
5123
The forth attribute is an auxiliary one and is used to calculate
5125
As the attribute dep_tables qualifies possibles orders of tables in the
5126
execution plan, the dependencies required by the straight join
5127
modifiers are reflected in this attribute as well.
5128
The function also removes all braces that can be removed from the join
5129
expression without changing its meaning.
5132
An outer join can be replaced by an inner join if the where condition
5133
or the on expression for an embedding nested join contains a conjunctive
5134
predicate rejecting null values for some attribute of the inner tables.
5138
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5140
the predicate t2.b < 5 rejects nulls.
5141
The query is converted first to:
5143
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5145
then to the equivalent form:
5147
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
5151
Similarly the following query:
5153
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
5158
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
5162
One conversion might trigger another:
5164
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
5165
LEFT JOIN t3 ON t3.b=t2.b
5166
WHERE t3 IS NOT NULL =>
5167
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
5168
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
5169
SELECT * FROM t1, t2, t3
5170
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
5173
The function removes all unnecessary braces from the expression
5174
produced by the conversions.
5177
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5179
finally is converted to:
5181
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5186
It also will remove braces from the following queries:
5188
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
5189
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
5192
The benefit of this simplification procedure is that it might return
5193
a query for which the optimizer can evaluate execution plan with more
5194
join orders. With a left join operation the optimizer does not
5195
consider any plan where one of the inner tables is before some of outer
5199
The function is implemented by a recursive procedure. On the recursive
5200
ascent all attributes are calculated, all outer joins that can be
5201
converted are replaced and then all unnecessary braces are removed.
5202
As join list contains join tables in the reverse order sequential
5203
elimination of outer joins does not require extra recursive calls.
5206
Remove all semi-joins that have are within another semi-join (i.e. have
5207
an "ancestor" semi-join nest)
5210
Here is an example of a join query with invalid cross references:
5212
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
5215
@param join reference to the query info
5216
@param join_list list representation of the join to be converted
5217
@param conds conditions to add on expressions for converted joins
5218
@param top true <=> conds is the where condition
5221
- The new condition, if success
5224
static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top)
5227
nested_join_st *nested_join;
5228
TableList *prev_table= 0;
5229
List_iterator<TableList> li(*join_list);
5232
Try to simplify join operations from join_list.
5233
The most outer join operation is checked for conversion first.
5235
while ((table= li++))
5237
table_map used_tables;
5238
table_map not_null_tables= (table_map) 0;
5240
if ((nested_join= table->getNestedJoin()))
5243
If the element of join_list is a nested join apply
5244
the procedure to its nested join list first.
5248
Item *expr= table->on_expr;
5250
If an on expression E is attached to the table,
5251
check all null rejected predicates in this expression.
5252
If such a predicate over an attribute belonging to
5253
an inner table of an embedded outer join is found,
5254
the outer join is converted to an inner join and
5255
the corresponding on expression is added to E.
5257
expr= simplify_joins(join, &nested_join->join_list, expr, false);
5259
if (!table->prep_on_expr || expr != table->on_expr)
5263
table->on_expr= expr;
5264
table->prep_on_expr= expr->copy_andor_structure(join->session);
5267
nested_join->used_tables= (table_map) 0;
5268
nested_join->not_null_tables=(table_map) 0;
5269
conds= simplify_joins(join, &nested_join->join_list, conds, top);
5270
used_tables= nested_join->used_tables;
5271
not_null_tables= nested_join->not_null_tables;
5275
if (!table->prep_on_expr)
5276
table->prep_on_expr= table->on_expr;
5277
used_tables= table->table->map;
5279
not_null_tables= conds->not_null_tables();
5282
if (table->getEmbedding())
5284
table->getEmbedding()->getNestedJoin()->used_tables|= used_tables;
5285
table->getEmbedding()->getNestedJoin()->not_null_tables|= not_null_tables;
5288
if (!table->outer_join || (used_tables & not_null_tables))
5291
For some of the inner tables there are conjunctive predicates
5292
that reject nulls => the outer join can be replaced by an inner join.
5294
table->outer_join= 0;
5297
/* Add ON expression to the WHERE or upper-level ON condition. */
5300
conds= and_conds(conds, table->on_expr);
5301
conds->top_level_item();
5302
/* conds is always a new item as both cond and on_expr existed */
5303
assert(!conds->fixed);
5304
conds->fix_fields(join->session, &conds);
5307
conds= table->on_expr;
5308
table->prep_on_expr= table->on_expr= 0;
5316
Only inner tables of non-convertible outer joins
5317
remain with on_expr.
5321
table->setDepTables(table->getDepTables() | table->on_expr->used_tables());
5322
if (table->getEmbedding())
5324
table->setDepTables(table->getDepTables() & ~table->getEmbedding()->getNestedJoin()->used_tables);
5326
Embedding table depends on tables used
5327
in embedded on expressions.
5329
table->getEmbedding()->setOnExprDepTables(table->getEmbedding()->getOnExprDepTables() & table->on_expr->used_tables());
5332
table->setDepTables(table->getDepTables() & ~table->table->map);
5337
//If this is straight join, set prev table to be dependent on all tables
5338
//from this nested join, so that correct join order is selected.
5339
if ((test(join->select_options & SELECT_STRAIGHT_JOIN)) ||
5340
prev_table->straight)
5341
prev_table->setDepTables(prev_table->getDepTables() | used_tables);
5342
if (prev_table->on_expr)
5344
prev_table->setDepTables(prev_table->getDepTables() | table->getOnExprDepTables());
5345
table_map prev_used_tables= prev_table->getNestedJoin() ?
5346
prev_table->getNestedJoin()->used_tables :
5347
prev_table->table->map;
5349
If on expression contains only references to inner tables
5350
we still make the inner tables dependent on the outer tables.
5351
It would be enough to set dependency only on one outer table
5352
for them. Yet this is really a rare case.
5354
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5355
prev_table->setDepTables(prev_table->getDepTables() | used_tables);
5362
Flatten nested joins that can be flattened.
5363
no ON expression and not a semi-join => can be flattened.
5366
while ((table= li++))
5368
nested_join= table->getNestedJoin();
5369
if (nested_join && !table->on_expr)
5372
List_iterator<TableList> it(nested_join->join_list);
5375
tbl->setEmbedding(table->getEmbedding());
5376
tbl->setJoinList(table->getJoinList());
5378
li.replace(nested_join->join_list);
5384
static int remove_duplicates(Join *join, Table *entry,List<Item> &fields, Item *having)
5387
uint32_t reclength,offset;
5388
uint32_t field_count;
5389
Session *session= join->session;
5391
entry->reginfo.lock_type=TL_WRITE;
5393
/* Calculate how many saved fields there is in list */
5395
List_iterator<Item> it(fields);
5399
if (item->get_tmp_table_field() && ! item->const_item())
5403
if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)
5404
{ // only const items with no OPTION_FOUND_ROWS
5405
join->unit->select_limit_cnt= 1; // Only send first row
5408
Field **first_field=entry->getFields() + entry->getShare()->sizeFields() - field_count;
5409
offset= (field_count ?
5410
entry->getField(entry->getShare()->sizeFields() - field_count)->offset(entry->getInsertRecord()) : 0);
5411
reclength= entry->getShare()->getRecordLength() - offset;
5413
entry->free_io_cache(); // Safety
5414
entry->cursor->info(HA_STATUS_VARIABLE);
5415
if (entry->getShare()->db_type() == heap_engine ||
5416
(!entry->getShare()->blob_fields &&
5417
((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->cursor->stats.records <
5418
session->variables.sortbuff_size)))
5420
error= remove_dup_with_hash_index(join->session, entry,
5421
field_count, first_field,
5426
error= remove_dup_with_compare(join->session, entry, first_field, offset, having);
5429
free_blobs(first_field);
5435
Function to setup clauses without sum functions.
5437
static int setup_without_group(Session *session,
5438
Item **ref_pointer_array,
5442
List<Item> &all_fields,
5446
bool *hidden_group_fields)
5449
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
5451
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5452
res= session->setup_conds(tables, conds);
5454
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
5455
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
5457
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5458
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
5459
group, hidden_group_fields);
5460
session->lex->allow_sum_func= save_allow_sum_func;
5465
Calculate the best possible join and initialize the join structure.
5472
static bool make_join_statistics(Join *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5477
uint32_t table_count;
5478
uint32_t const_count;
5480
table_map found_const_table_map;
5481
table_map all_table_map;
5482
table_map found_ref;
5486
Table **table_vector= NULL;
5487
JoinTable *stat= NULL;
5488
JoinTable *stat_end= NULL;
5490
JoinTable **stat_ref= NULL;
5491
optimizer::KeyUse *keyuse= NULL;
5492
optimizer::KeyUse *start_keyuse= NULL;
5493
table_map outer_join= 0;
5494
vector<optimizer::SargableParam> sargables;
5495
JoinTable *stat_vector[MAX_TABLES+1];
5496
optimizer::Position *partial_pos;
5498
table_count= join->tables;
5499
stat= (JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
5500
stat_ref= (JoinTable**) join->session->alloc(sizeof(JoinTable*)*MAX_TABLES);
5501
table_vector= (Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
5502
if (! stat || ! stat_ref || ! table_vector)
5505
join->best_ref=stat_vector;
5507
stat_end=stat+table_count;
5508
found_const_table_map= all_table_map=0;
5513
s++, tables= tables->next_leaf, i++)
5515
TableList *embedding= tables->getEmbedding();
5518
s->const_keys.reset();
5519
s->checked_keys.reset();
5520
s->needed_reg.reset();
5521
table_vector[i]=s->table=table=tables->table;
5522
table->pos_in_table_list= tables;
5523
assert(table->cursor);
5524
error= table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5527
table->print_error(error, MYF(0));
5530
table->quick_keys.reset();
5531
table->reginfo.join_tab=s;
5532
table->reginfo.not_exists_optimize=0;
5533
memset(table->const_key_parts, 0,
5534
sizeof(key_part_map)*table->getShare()->sizeKeys());
5535
all_table_map|= table->map;
5537
s->info=0; // For describe
5539
s->dependent= tables->getDepTables();
5540
s->key_dependent= 0;
5541
table->quick_condition_rows= table->cursor->stats.records;
5543
s->on_expr_ref= &tables->on_expr;
5544
if (*s->on_expr_ref)
5546
/* s is the only inner table of an outer join */
5547
if (!table->cursor->stats.records && !embedding)
5549
s->dependent= 0; // Ignore LEFT JOIN depend.
5550
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5553
outer_join|= table->map;
5554
s->embedding_map.reset();
5555
for (;embedding; embedding= embedding->getEmbedding())
5556
s->embedding_map|= embedding->getNestedJoin()->nj_map;
5559
if (embedding && !(false && ! embedding->getEmbedding()))
5561
/* s belongs to a nested join, maybe to several embedded joins */
5562
s->embedding_map.reset();
5565
nested_join_st *nested_join= embedding->getNestedJoin();
5566
s->embedding_map|= nested_join->nj_map;
5567
s->dependent|= embedding->getDepTables();
5568
embedding= embedding->getEmbedding();
5569
outer_join|= nested_join->used_tables;
5574
if ((table->cursor->stats.records <= 1) && !s->dependent &&
5575
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5576
!join->no_const_tables)
5578
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5582
join->outer_join=outer_join;
5584
if (join->outer_join)
5587
Build transitive closure for relation 'to be dependent on'.
5588
This will speed up the plan search for many cases with outer joins,
5589
as well as allow us to catch illegal cross references/
5590
Warshall's algorithm is used to build the transitive closure.
5591
As we use bitmaps to represent the relation the complexity
5592
of the algorithm is O((number of tables)^2).
5594
for (i= 0, s= stat ; i < table_count ; i++, s++)
5596
for (uint32_t j= 0 ; j < table_count ; j++)
5598
table= stat[j].table;
5599
if (s->dependent & table->map)
5600
s->dependent |= table->reginfo.join_tab->dependent;
5603
s->table->maybe_null= 1;
5605
/* Catch illegal cross references for outer joins */
5606
for (i= 0, s= stat ; i < table_count ; i++, s++)
5608
if (s->dependent & s->table->map)
5610
join->tables=0; // Don't use join->table
5611
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
5614
s->key_dependent= s->dependent;
5618
if (conds || outer_join)
5619
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
5620
conds, join->cond_equal,
5621
~outer_join, join->select_lex, sargables))
5624
/* Read tables with 0 or 1 rows (system tables) */
5625
join->const_table_map= 0;
5627
optimizer::Position *p_pos= join->getFirstPosInPartialPlan();
5628
optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5629
while (p_pos < p_end)
5632
s= p_pos->getJoinTable();
5634
join->const_table_map|=s->table->map;
5635
if ((tmp= join_read_const_table(s, p_pos)))
5638
return 1; // Fatal error
5641
found_const_table_map|= s->table->map;
5645
/* loop until no more const tables are found */
5649
more_const_tables_found:
5654
We only have to loop from stat_vector + const_count as
5655
set_position() will move all const_tables first in stat_vector
5658
for (JoinTable **pos= stat_vector+const_count; (s= *pos); pos++)
5663
If equi-join condition by a key is null rejecting and after a
5664
substitution of a const table the key value happens to be null
5665
then we can state that there are no matches for this equi-join.
5667
if ((keyuse= s->keyuse) && *s->on_expr_ref && s->embedding_map.none())
5670
When performing an outer join operation if there are no matching rows
5671
for the single row of the outer table all the inner tables are to be
5672
null complemented and thus considered as constant tables.
5673
Here we apply this consideration to the case of outer join operations
5674
with a single inner table only because the case with nested tables
5675
would require a more thorough analysis.
5676
TODO. Apply single row substitution to null complemented inner tables
5677
for nested outer join operations.
5679
while (keyuse->getTable() == table)
5681
if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&
5682
keyuse->getVal()->is_null() && keyuse->isNullRejected())
5685
table->mark_as_null_row();
5686
found_const_table_map|= table->map;
5687
join->const_table_map|= table->map;
5688
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5689
goto more_const_tables_found;
5695
if (s->dependent) // If dependent on some table
5697
// All dep. must be constants
5698
if (s->dependent & ~(found_const_table_map))
5700
if (table->cursor->stats.records <= 1L &&
5701
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5702
!table->pos_in_table_list->getEmbedding())
5706
join->const_table_map|=table->map;
5707
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5708
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5709
if ((tmp= join_read_const_table(s, partial_pos)))
5712
return 1; // Fatal error
5715
found_const_table_map|= table->map;
5719
/* check if table can be read by key or table only uses const refs */
5720
if ((keyuse=s->keyuse))
5723
while (keyuse->getTable() == table)
5725
start_keyuse= keyuse;
5726
key= keyuse->getKey();
5727
s->keys.set(key); // QQ: remove this ?
5734
if (keyuse->getVal()->type() != Item::NULL_ITEM &&
5735
! keyuse->getOptimizeFlags())
5737
if (! ((~found_const_table_map) & keyuse->getUsedTables()))
5738
const_ref.set(keyuse->getKeypart());
5740
refs|= keyuse->getUsedTables();
5741
eq_part.set(keyuse->getKeypart());
5744
} while (keyuse->getTable() == table && keyuse->getKey() == key);
5746
if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
5747
! table->pos_in_table_list->getEmbedding())
5749
if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
5751
if (const_ref == eq_part)
5752
{ // Found everything for ref.
5756
join->const_table_map|= table->map;
5757
set_position(join, const_count++, s, start_keyuse);
5758
if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
5760
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5761
if ((tmp=join_read_const_table(s, partial_pos)))
5764
return 1; // Fatal error
5767
found_const_table_map|= table->map;
5771
found_ref|= refs; // Table is const if all refs are const
5773
else if (const_ref == eq_part)
5774
s->const_keys.set(key);
5779
} while (join->const_table_map & found_ref && ref_changed);
5782
Update info on indexes that can be used for search lookups as
5783
reading const tables may has added new sargable predicates.
5785
if (const_count && ! sargables.empty())
5787
vector<optimizer::SargableParam>::iterator iter= sargables.begin();
5788
while (iter != sargables.end())
5790
Field *field= (*iter).getField();
5791
JoinTable *join_tab= field->getTable()->reginfo.join_tab;
5792
key_map possible_keys= field->key_start;
5793
possible_keys&= field->getTable()->keys_in_use_for_query;
5794
bool is_const= true;
5795
for (uint32_t j= 0; j < (*iter).getNumValues(); j++)
5796
is_const&= (*iter).isConstItem(j);
5798
join_tab[0].const_keys|= possible_keys;
5803
/* Calc how many (possible) matched records in each table */
5805
for (s=stat ; s < stat_end ; s++)
5807
if (s->type == AM_SYSTEM || s->type == AM_CONST)
5809
/* Only one matching row */
5810
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
5813
/* Approximate found rows and time to read them */
5814
s->found_records=s->records=s->table->cursor->stats.records;
5815
s->read_time=(ha_rows) s->table->cursor->scan_time();
5818
Set a max range of how many seeks we can expect when using keys
5819
This is can't be to high as otherwise we are likely to use
5822
s->worst_seeks= min((double) s->found_records / 10,
5823
(double) s->read_time*3);
5824
if (s->worst_seeks < 2.0) // Fix for small tables
5828
Add to stat->const_keys those indexes for which all group fields or
5829
all select distinct fields participate in one index.
5831
add_group_and_distinct_keys(join, s);
5833
if (s->const_keys.any() &&
5834
!s->table->pos_in_table_list->getEmbedding())
5837
optimizer::SqlSelect *select= NULL;
5838
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);
5841
records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
5842
s->quick=select->quick;
5843
s->needed_reg=select->needed_reg;
5845
if (records == 0 && s->table->reginfo.impossible_range)
5848
Impossible WHERE or ON expression
5849
In case of ON, we mark that the we match one empty NULL row.
5850
In case of WHERE, don't set found_const_table_map to get the
5851
caller to abort with a zero row result.
5853
join->const_table_map|= s->table->map;
5854
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5856
if (*s->on_expr_ref)
5858
/* Generate empty row */
5859
s->info= "Impossible ON condition";
5860
found_const_table_map|= s->table->map;
5862
s->table->mark_as_null_row(); // All fields are NULL
5865
if (records != HA_POS_ERROR)
5867
s->found_records=records;
5868
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
5874
join->join_tab=stat;
5875
join->map2table=stat_ref;
5876
join->table= join->all_tables=table_vector;
5877
join->const_tables=const_count;
5878
join->found_const_table_map=found_const_table_map;
5880
/* Find an optimal join order of the non-constant tables. */
5881
if (join->const_tables != join->tables)
5883
optimize_keyuse(join, keyuse_array);
5884
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->query.c_str(), join->session->thread_id);
5885
bool res= choose_plan(join, all_table_map & ~join->const_table_map);
5886
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);
5892
join->copyPartialPlanIntoOptimalPlan(join->const_tables);
5893
join->best_read= 1.0;
5895
/* Generate an execution plan from the found optimal join order. */
5896
return (join->session->killed || get_best_combination(join));
5900
Assign each nested join structure a bit in the nested join bitset.
5902
Assign each nested join structure (except "confluent" ones - those that
5903
embed only one element) a bit in the nested join bitset.
5905
@param join Join being processed
5906
@param join_list List of tables
5907
@param first_unused Number of first unused bit in the nest joing bitset before the
5911
This function is called after simplify_joins(), when there are no
5912
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
5913
we will not run out of bits in the nested join bitset.
5916
First unused bit in the nest join bitset after the call.
5918
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
5920
List_iterator<TableList> li(*join_list);
5922
while ((table= li++))
5924
nested_join_st *nested_join;
5925
if ((nested_join= table->getNestedJoin()))
5928
It is guaranteed by simplify_joins() function that a nested join
5929
that has only one child is either
5930
- a single-table view (the child is the underlying table), or
5931
- a single-table semi-join nest
5933
We don't assign bits to such sj-nests because
5934
1. it is redundant (a "sequence" of one table cannot be interleaved
5936
2. we could run out of bits in the nested join bitset otherwise.
5938
if (nested_join->join_list.elements != 1)
5940
/* Don't assign bits to sj-nests */
5942
nested_join->nj_map.set(first_unused++);
5943
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
5948
return(first_unused);
5953
Return table number if there is only one table in sort order
5954
and group and order is compatible, else return 0.
5956
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables)
5958
table_map map= (table_map) 0;
5961
a= b; // Only one need to be given
5965
for (; a && b; a=a->next,b=b->next)
5967
if (!(*a->item)->eq(*b->item,1))
5968
return (Table *) NULL;
5969
map|= a->item[0]->used_tables();
5971
if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
5972
return (Table *) NULL;
5974
for (; !(map & tables->table->map); tables= tables->next_leaf) {};
5975
if (map != tables->table->map)
5976
return (Table *) NULL; // More than one table
5977
return tables->table;
5981
Set nested_join_st::counter=0 in all nested joins in passed list.
5983
Recursively set nested_join_st::counter=0 for all nested joins contained in
5984
the passed join_list.
5986
@param join_list List of nested joins to process. It may also contain base
5987
tables which will be ignored.
5989
static void reset_nj_counters(List<TableList> *join_list)
5991
List_iterator<TableList> li(*join_list);
5993
while ((table= li++))
5995
nested_join_st *nested_join;
5996
if ((nested_join= table->getNestedJoin()))
5998
nested_join->counter_= 0;
5999
reset_nj_counters(&nested_join->join_list);
6006
Return 1 if second is a subpart of first argument.
6008
If first parts has different direction, change it to second part
6009
(group is sorted like order)
6011
static bool test_if_subpart(order_st *a,order_st *b)
6013
for (; a && b; a=a->next,b=b->next)
6015
if ((*a->item)->eq(*b->item,1))
6024
Nested joins perspective: Remove the last table from the join order.
6026
The algorithm is the reciprocal of check_interleaving_with_nj(), hence
6027
parent join nest nodes are updated only when the last table in its child
6028
node is removed. The ASCII graphic below will clarify.
6030
%A table nesting such as <tt> t1 x [ ( t2 x t3 ) x ( t4 x t5 ) ] </tt>is
6031
represented by the below join nest tree.
6039
t1 x [ (t2 x t3) x (t4 x t5) ]
6042
At the point in time when check_interleaving_with_nj() adds the table t5 to
6043
the query execution plan, QEP, it also directs the node named NJ2 to mark
6044
the table as covered. NJ2 does so by incrementing its @c counter
6045
member. Since all of NJ2's tables are now covered by the QEP, the algorithm
6046
proceeds up the tree to NJ1, incrementing its counter as well. All join
6047
nests are now completely covered by the QEP.
6049
restore_prev_nj_state() does the above in reverse. As seen above, the node
6050
NJ1 contains the nodes t2, t3, and NJ2. Its counter being equal to 3 means
6051
that the plan covers t2, t3, and NJ2, @e and that the sub-plan (t4 x t5)
6052
completely covers NJ2. The removal of t5 from the partial plan will first
6053
decrement NJ2's counter to 1. It will then detect that NJ2 went from being
6054
completely to partially covered, and hence the algorithm must continue
6055
upwards to NJ1 and decrement its counter to 2. %A subsequent removal of t4
6056
will however not influence NJ1 since it did not un-cover the last table in
6060
restore_prev_nj_state()
6061
last join table to remove, it is assumed to be the last in current
6066
Remove the last table from the partial join order and update the nested
6067
joins counters and join->cur_embedding_map. It is ok to call this
6068
function for the first table in join order (for which
6069
check_interleaving_with_nj has not been called)
6071
@param last join table to remove, it is assumed to be the last in current
6075
static void restore_prev_nj_state(JoinTable *last)
6077
TableList *last_emb= last->table->pos_in_table_list->getEmbedding();
6078
Join *join= last->join;
6079
for (;last_emb != NULL; last_emb= last_emb->getEmbedding())
6081
nested_join_st *nest= last_emb->getNestedJoin();
6083
bool was_fully_covered= nest->is_fully_covered();
6085
if (--nest->counter_ == 0)
6086
join->cur_embedding_map&= ~nest->nj_map;
6088
if (!was_fully_covered)
6091
join->cur_embedding_map|= nest->nj_map;
6096
Create a condition for a const reference and add this to the
6097
currenct select for the table.
6099
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)
6101
if (!join_tab->ref.key_parts)
6104
Item_cond_and *cond=new Item_cond_and();
6105
Table *table=join_tab->table;
6110
for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6112
Field *field=table->getField(table->key_info[join_tab->ref.key].key_part[i].fieldnr - 1);
6113
Item *value=join_tab->ref.items[i];
6114
cond->add(new Item_func_equal(new Item_field(field), value));
6116
if (session->is_fatal_error)
6120
cond->fix_fields(session, (Item**)&cond);
6121
if (join_tab->select)
6123
error=(int) cond->add(join_tab->select->cond);
6124
join_tab->select_cond=join_tab->select->cond=cond;
6126
else if ((join_tab->select= optimizer::make_select(join_tab->table, 0, 0, cond, 0,
6128
join_tab->select_cond=cond;
6130
return(error ? true : false);
6133
static void free_blobs(Field **ptr)
6135
for (; *ptr ; ptr++)
6137
if ((*ptr)->flags & BLOB_FLAG)
6138
((Field_blob *) (*ptr))->free();
6143
@} (end of group Query_Optimizer)
6146
} /* namespace drizzled */
added
removed
drizzled/join.cc
