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, Inc.
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 *group);
75
static bool alloc_group_fields(Join *join, Order *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 *order);
106
static Order *remove_constants(Join *join,Order *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 *a, Order *b,TableList *tables);
130
static void reset_nj_counters(List<TableList> *join_list);
131
static bool test_if_subpart(Order *a,Order *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,
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)
200
if (setup_wild(session, fields_list, &all_fields, wild_num) ||
201
select_lex->setup_ref_array(session, og_num) ||
202
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
204
setup_without_group(session, (*rref_pointer_array), tables_list,
205
select_lex->leaf_tables, fields_list,
206
all_fields, &conds, order, group_list,
207
&hidden_group_fields))
210
ref_pointer_array= *rref_pointer_array;
214
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
215
session->where="having clause";
216
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
217
select_lex->having_fix_field= 1;
218
bool having_fix_rc= (!having->fixed &&
219
(having->fix_fields(session, &having) ||
220
having->check_cols(1)));
221
select_lex->having_fix_field= 0;
222
if (having_fix_rc || session->is_error())
224
session->lex->allow_sum_func= save_allow_sum_func;
228
Item_subselect *subselect;
229
Item_in_subselect *in_subs= NULL;
231
Are we in a subquery predicate?
232
TODO: the block below will be executed for every PS execution without need.
234
if ((subselect= select_lex->master_unit()->item))
236
if (subselect->substype() == Item_subselect::IN_SUBS)
237
in_subs= (Item_in_subselect*)subselect;
240
bool do_materialize= true;
242
Check if the subquery predicate can be executed via materialization.
243
The required conditions are:
244
1. Subquery predicate is an IN/=ANY subq predicate
245
2. Subquery is a single SELECT (not a UNION)
246
3. Subquery is not a table-less query. In this case there is no
247
point in materializing.
248
4. Subquery predicate is a top-level predicate
249
(this implies it is not negated)
250
TODO: this is a limitation that should be lifeted once we
251
implement correct NULL semantics (WL#3830)
252
5. Subquery is non-correlated
254
This is an overly restrictive condition. It can be extended to:
255
(Subquery is non-correlated ||
256
Subquery is correlated to any query outer to IN predicate ||
257
(Subquery is correlated to the immediate outer query &&
258
Subquery !contains {GROUP BY, ORDER BY [LIMIT],
259
aggregate functions) && subquery predicate is not under "NOT IN"))
260
6. No execution method was already chosen (by a prepared statement).
262
(*) The subquery must be part of a SELECT statement. The current
263
condition also excludes multi-table update statements.
265
We have to determine whether we will perform subquery materialization
266
before calling the IN=>EXISTS transformation, so that we know whether to
267
perform the whole transformation or only that part of it which wraps
268
Item_in_subselect in an Item_in_optimizer.
270
if (do_materialize &&
272
!select_lex->master_unit()->first_select()->next_select() && // 2
273
select_lex->master_unit()->first_select()->leaf_tables && // 3
274
session->lex->sql_command == SQLCOM_SELECT) // *
276
if (in_subs->is_top_level_item() && // 4
277
!in_subs->is_correlated && // 5
278
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
279
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
282
Item_subselect::trans_res trans_res;
283
if ((trans_res= subselect->select_transformer(this)) !=
284
Item_subselect::RES_OK)
286
return((trans_res == Item_subselect::RES_ERROR));
295
for (ord= order; ord; ord= ord->next)
297
Item *item= *ord->item;
298
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
299
item->split_sum_func(session, ref_pointer_array, all_fields);
303
if (having && having->with_sum_func)
304
having->split_sum_func(session, ref_pointer_array, all_fields,
306
if (select_lex->inner_sum_func_list)
308
Item_sum *end=select_lex->inner_sum_func_list;
309
Item_sum *item_sum= end;
312
item_sum= item_sum->next;
313
item_sum->split_sum_func(session, ref_pointer_array,
314
all_fields, item_sum->ref_by, false);
315
} while (item_sum != end);
318
if (select_lex->inner_refs_list.elements &&
319
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
323
Check if there are references to un-aggregated columns when computing
324
aggregate functions with implicit grouping (there is no GROUP BY).
326
MODE_ONLY_FULL_GROUP_BY is enabled here by default
329
select_lex->full_group_by_flag.test(NON_AGG_FIELD_USED) &&
330
select_lex->full_group_by_flag.test(SUM_FUNC_USED))
332
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
333
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
337
/* Caclulate the number of groups */
339
for (Order *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
347
* The below will create the new table for
348
* CREATE TABLE ... SELECT
350
* @see create_table_from_items() in drizzled/sql_insert.cc
352
if (result && result->prepare(fields_list, unit_arg))
355
/* Init join struct */
356
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
357
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
358
this->group= group_list != 0;
361
#ifdef RESTRICTED_GROUP
362
if (sum_func_count && !group_list && (func_count || field_count))
364
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
368
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
371
if (alloc_func_list())
378
Remove the predicates pushed down into the subquery
381
Join::remove_subq_pushed_predicates()
382
where IN Must be NULL
383
OUT The remaining WHERE condition, or NULL
386
Given that this join will be executed using (unique|index)_subquery,
387
without "checking NULL", remove the predicates that were pushed down
390
If the subquery compares scalar values, we can remove the condition that
391
was wrapped into trig_cond (it will be checked when needed by the subquery
394
If the subquery compares row values, we need to keep the wrapped
395
equalities in the WHERE clause: when the left (outer) tuple has both NULL
396
and non-NULL values, we'll do a full table scan and will rely on the
397
equalities corresponding to non-NULL parts of left tuple to filter out
398
non-matching records.
400
TODO: We can remove the equalities that will be guaranteed to be true by the
401
fact that subquery engine will be using index lookup. This must be done only
402
for cases where there are no conversion errors of significance, e.g. 257
403
that is searched in a byte. But this requires homogenization of the return
404
codes of all Field*::store() methods.
406
void Join::remove_subq_pushed_predicates(Item **where)
408
if (conds->type() == Item::FUNC_ITEM &&
409
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
410
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
411
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
412
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
413
((Item_func *)conds)->arguments()[0]))
421
global select optimisation.
424
error code saved in field 'error'
433
// to prevent double initialization on EXPLAIN
438
session->set_proc_info("optimizing");
439
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
440
unit->select_limit_cnt);
441
/* select_limit is used to decide if we are likely to scan the whole table */
442
select_limit= unit->select_limit_cnt;
443
if (having || (select_options & OPTION_FOUND_ROWS))
444
select_limit= HA_POS_ERROR;
445
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
446
// Ignore errors of execution if option IGNORE present
447
if (session->lex->ignore)
448
session->lex->current_select->no_error= 1;
450
#ifdef HAVE_REF_TO_FIELDS // Not done yet
451
/* Add HAVING to WHERE if possible */
452
if (having && !group_list && !sum_func_count)
459
else if ((conds=new Item_cond_and(conds,having)))
462
Item_cond_and can't be fixed after creation, so we do not check
465
conds->fix_fields(session, &conds);
466
conds->change_ref_to_fields(session, tables_list);
467
conds->top_level_item();
473
/* Convert all outer joins to inner joins if possible */
474
conds= simplify_joins(this, join_list, conds, true);
475
build_bitmap_for_nested_joins(join_list, 0);
477
conds= optimize_cond(this, conds, join_list, &cond_value);
478
if (session->is_error())
485
having= optimize_cond(this, having, join_list, &having_value);
486
if (session->is_error())
491
if (select_lex->where)
492
select_lex->cond_value= cond_value;
493
if (select_lex->having)
494
select_lex->having_value= having_value;
496
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
497
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
498
{ /* Impossible cond */
499
zero_result_cause= having_value == Item::COND_FALSE ?
500
"Impossible HAVING" : "Impossible WHERE";
502
goto setup_subq_exit;
506
/* Optimize count(*), cmin() and cmax() */
507
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
511
optimizer::sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
512
to the WHERE conditions,
513
or 1 if all items were resolved,
514
or 0, or an error number HA_ERR_...
516
if ((res= optimizer::sum_query(select_lex->leaf_tables, all_fields, conds)))
518
if (res == HA_ERR_KEY_NOT_FOUND)
520
zero_result_cause= "No matching min/max row";
522
goto setup_subq_exit;
531
zero_result_cause= "No matching min/max row";
533
goto setup_subq_exit;
535
zero_result_cause= "Select tables optimized away";
536
tables_list= 0; // All tables resolved
537
const_tables= tables;
539
Extract all table-independent conditions and replace the WHERE
540
clause with them. All other conditions were computed by optimizer::sum_query
541
and the MIN/MAX/COUNT function(s) have been replaced by constants,
542
so there is no need to compute the whole WHERE clause again.
543
Notice that make_cond_for_table() will always succeed to remove all
544
computed conditions, because optimizer::sum_query() is applicable only to
546
Preserve conditions for EXPLAIN.
548
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
550
COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
551
conds= table_independent_conds;
553
goto setup_subq_exit;
561
error= -1; // Error is sent to client
562
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
564
/* Calculate how to do the join */
565
session->set_proc_info("statistics");
566
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
567
session->is_fatal_error)
572
/* Remove distinct if only const tables */
573
select_distinct= select_distinct && (const_tables != tables);
574
session->set_proc_info("preparing");
575
if (result->initialize_tables(this))
577
return 1; // error == -1
579
if (const_table_map != found_const_table_map &&
580
!(select_options & SELECT_DESCRIBE) &&
582
!(conds->used_tables() & RAND_TABLE_BIT) ||
583
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
585
zero_result_cause= "no matching row in const table";
586
goto setup_subq_exit;
588
if (!(session->options & OPTION_BIG_SELECTS) &&
589
best_read > (double) session->variables.max_join_size &&
590
!(select_options & SELECT_DESCRIBE))
592
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
596
if (const_tables && !(select_options & SELECT_NO_UNLOCK))
597
session->unlockSomeTables(table, const_tables);
598
if (!conds && outer_join)
600
/* Handle the case where we have an OUTER JOIN without a WHERE */
601
conds=new Item_int((int64_t) 1,1); // Always true
603
select= optimizer::make_select(*table, const_table_map,
604
const_table_map, conds, 1, &error);
611
reset_nj_counters(join_list);
612
make_outerjoin_info(this);
615
Among the equal fields belonging to the same multiple equality
616
choose the one that is to be retrieved first and substitute
617
all references to these in where condition for a reference for
622
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
623
conds->update_used_tables();
627
Permorm the the optimization on fields evaluation mentioned above
628
for all on expressions.
630
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
632
if (*tab->on_expr_ref)
634
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
637
(*tab->on_expr_ref)->update_used_tables();
641
if (conds &&!outer_join && const_table_map != found_const_table_map &&
642
(select_options & SELECT_DESCRIBE) &&
643
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
645
conds=new Item_int((int64_t) 0,1); // Always false
648
if (make_join_select(this, select, conds))
651
"Impossible WHERE noticed after reading const tables";
652
goto setup_subq_exit;
655
error= -1; /* if goto err */
657
/* Optimize distinct away if possible */
659
Order *org_order= order;
660
order= remove_constants(this, order,conds,1, &simple_order);
661
if (session->is_error())
668
If we are using ORDER BY NULL or ORDER BY const_expression,
669
return result in any order (even if we are using a GROUP BY)
671
if (!order && org_order)
675
Check if we can optimize away GROUP BY/DISTINCT.
676
We can do that if there are no aggregate functions, the
677
fields in DISTINCT clause (if present) and/or columns in GROUP BY
678
(if present) contain direct references to all key parts of
679
an unique index (in whatever order) and if the key parts of the
680
unique index cannot contain NULLs.
681
Note that the unique keys for DISTINCT and GROUP BY should not
682
be the same (as long as they are unique).
684
The FROM clause must contain a single non-constant table.
686
if (tables - const_tables == 1 && (group_list || select_distinct) &&
687
! tmp_table_param.sum_func_count &&
688
(! join_tab[const_tables].select ||
689
! join_tab[const_tables].select->quick ||
690
join_tab[const_tables].select->quick->get_type() !=
691
optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))
693
if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
696
We have found that grouping can be removed since groups correspond to
697
only one row anyway, but we still have to guarantee correct result
698
order. The line below effectively rewrites the query from GROUP BY
699
<fields> to ORDER BY <fields>. There are two exceptions:
700
- if skip_sort_order is set (see above), then we can simply skip
702
- we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'
703
with the GROUP BY ones, i.e. either one is a prefix of another.
704
We only check if the ORDER BY is a prefix of GROUP BY. In this case
705
test_if_subpart() copies the ASC/DESC attributes from the original
707
If GROUP BY is a prefix of order_st BY, then it is safe to leave
710
if (! order || test_if_subpart(group_list, order))
711
order= skip_sort_order ? 0 : group_list;
713
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
714
rewritten to IGNORE INDEX FOR order_st BY(fields).
716
join_tab->table->keys_in_use_for_order_by=
717
join_tab->table->keys_in_use_for_group_by;
721
if (select_distinct &&
722
list_contains_unique_index(join_tab[const_tables].table,
723
find_field_in_item_list,
724
(void *) &fields_list))
729
if (group_list || tmp_table_param.sum_func_count)
731
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
734
else if (select_distinct && tables - const_tables == 1)
737
We are only using one table. In this case we change DISTINCT to a
739
- The GROUP BY can be done through indexes (no sort) and the order_st
740
BY only uses selected fields.
741
(In this case we can later optimize away GROUP BY and order_st BY)
742
- We are scanning the whole table without LIMIT
744
- We are using CALC_FOUND_ROWS
745
- We are using an ORDER BY that can't be optimized away.
747
We don't want to use this optimization when we are using LIMIT
748
because in this case we can just create a temporary table that
749
holds LIMIT rows and stop when this table is full.
751
JoinTable *tab= &join_tab[const_tables];
752
bool all_order_fields_used;
754
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
755
&tab->table->keys_in_use_for_order_by);
756
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
757
order, fields_list, all_fields,
758
&all_order_fields_used)))
760
bool skip_group= (skip_sort_order &&
761
test_if_skip_sort_order(tab, group_list, select_limit, 1,
762
&tab->table->keys_in_use_for_group_by) != 0);
763
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
764
if ((skip_group && all_order_fields_used) ||
765
select_limit == HA_POS_ERROR ||
766
(order && !skip_sort_order))
768
/* Change DISTINCT to GROUP BY */
771
if (all_order_fields_used)
773
if (order && skip_sort_order)
776
Force MySQL to read the table in sorted order to get result in
779
tmp_table_param.quick_group=0;
783
group=1; // For end_write_group
788
else if (session->is_fatal_error) // End of memory
793
Order *old_group_list;
794
group_list= remove_constants(this, (old_group_list= group_list), conds,
795
rollup.state == ROLLUP::STATE_NONE,
797
if (session->is_error())
802
if (old_group_list && !group_list)
805
if (!group_list && group)
807
order=0; // The output has only one row
809
select_distinct= 0; // No need in distinct for 1 row
810
group_optimized_away= 1;
813
calc_group_buffer(this, group_list);
814
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
816
if (test_if_subpart(group_list, order) ||
817
(!group_list && tmp_table_param.sum_func_count))
820
// Can't use sort on head table if using row cache
830
Check if we need to create a temporary table.
831
This has to be done if all tables are not already read (const tables)
832
and one of the following conditions holds:
833
- We are using DISTINCT (simple distinct's are already optimized away)
834
- We are using an ORDER BY or GROUP BY on fields not in the first table
835
- We are using different ORDER BY and GROUP BY orders
836
- The user wants us to buffer the result.
838
need_tmp= (const_tables != tables &&
839
((select_distinct || !simple_order || !simple_group) ||
840
(group_list && order) ||
841
test(select_options & OPTION_BUFFER_RESULT)));
843
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
844
if (make_join_readinfo(this))
847
/* Create all structures needed for materialized subquery execution. */
848
if (setup_subquery_materialization())
851
/* Cache constant expressions in WHERE, HAVING, ON clauses. */
855
is this simple IN subquery?
857
if (!group_list && !order &&
858
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
859
tables == 1 && conds &&
865
if (join_tab[0].type == AM_EQ_REF && join_tab[0].ref.items[0]->name == in_left_expr_name)
867
remove_subq_pushed_predicates(&where);
868
save_index_subquery_explain_info(join_tab, where);
869
join_tab[0].type= AM_UNIQUE_SUBQUERY;
871
return(unit->item->change_engine(new subselect_uniquesubquery_engine(session, join_tab, unit->item, where)));
873
else if (join_tab[0].type == AM_REF &&
874
join_tab[0].ref.items[0]->name == in_left_expr_name)
876
remove_subq_pushed_predicates(&where);
877
save_index_subquery_explain_info(join_tab, where);
878
join_tab[0].type= AM_INDEX_SUBQUERY;
880
return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, where, NULL, 0)));
883
else if (join_tab[0].type == AM_REF_OR_NULL &&
884
join_tab[0].ref.items[0]->name == in_left_expr_name &&
885
having->name == in_having_cond)
887
join_tab[0].type= AM_INDEX_SUBQUERY;
889
conds= remove_additional_cond(conds);
890
save_index_subquery_explain_info(join_tab, conds);
891
return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, conds, having, 1)));
896
Need to tell handlers that to play it safe, it should fetch all
897
columns of the primary key of the tables: this is because MySQL may
898
build row pointers for the rows, and for all columns of the primary key
899
the read set has not necessarily been set by the server code.
901
if (need_tmp || select_distinct || group_list || order)
903
for (uint32_t i = const_tables; i < tables; i++)
904
join_tab[i].table->prepare_for_position();
907
if (const_tables != tables)
910
Because filesort always does a full table scan or a quick range scan
911
we must add the removed reference to the select for the table.
912
We only need to do this when we have a simple_order or simple_group
913
as in other cases the join is done before the sort.
915
if ((order || group_list) &&
916
(join_tab[const_tables].type != AM_ALL) &&
917
(join_tab[const_tables].type != AM_REF_OR_NULL) &&
918
((order && simple_order) || (group_list && simple_group)))
920
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
925
if (!(select_options & SELECT_BIG_RESULT) &&
928
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
929
unit->select_limit_cnt, 0,
930
&join_tab[const_tables].table->
931
keys_in_use_for_group_by))) ||
933
tmp_table_param.quick_group)
935
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
940
Force using of tmp table if sorting by a SP or UDF function due to
941
their expensive and probably non-deterministic nature.
943
for (Order *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
945
Item *item= *tmp_order->item;
946
if (item->is_expensive())
948
/* Force tmp table without sort */
949
need_tmp=1; simple_order=simple_group=0;
957
if (select_options & SELECT_DESCRIBE)
965
The loose index scan access method guarantees that all grouping or
966
duplicate row elimination (for distinct) is already performed
967
during data retrieval, and that all MIN/MAX functions are already
968
computed for each group. Thus all MIN/MAX functions should be
969
treated as regular functions, and there is no need to perform
970
grouping in the main execution loop.
971
Notice that currently loose index scan is applicable only for
972
single table queries, thus it is sufficient to test only the first
973
join_tab element of the plan for its access method.
975
if (join_tab->is_using_loose_index_scan())
976
tmp_table_param.precomputed_group_by= true;
978
/* Create a tmp table if distinct or if the sort is too complicated */
981
session->set_proc_info("Creating tmp table");
983
init_items_ref_array();
985
tmp_table_param.hidden_field_count= (all_fields.elements -
986
fields_list.elements);
987
Order *tmp_group= ((!simple_group &&
988
! (test_flags.test(TEST_NO_KEY_GROUP))) ? group_list :
991
Pushing LIMIT to the temporary table creation is not applicable
992
when there is ORDER BY or GROUP BY or there is no GROUP BY, but
993
there are aggregate functions, because in all these cases we need
996
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
998
!session->lex->current_select->with_sum_func) ?
999
select_limit : HA_POS_ERROR;
1001
if (!(exec_tmp_table1=
1002
create_tmp_table(session, &tmp_table_param, all_fields,
1004
group_list ? 0 : select_distinct,
1005
group_list && simple_group,
1014
We don't have to store rows in temp table that doesn't match HAVING if:
1015
- we are sorting the table and writing complete group rows to the
1017
- We are using DISTINCT without resolving the distinct as a GROUP BY
1020
If having is not handled here, it will be checked before the row
1021
is sent to the client.
1023
if (tmp_having && (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1026
/* if group or order on first table, sort first */
1027
if (group_list && simple_group)
1029
session->set_proc_info("Sorting for group");
1030
if (create_sort_index(session, this, group_list,
1031
HA_POS_ERROR, HA_POS_ERROR, false) ||
1032
alloc_group_fields(this, group_list) ||
1033
make_sum_func_list(all_fields, fields_list, 1) ||
1034
setup_sum_funcs(session, sum_funcs))
1042
if (make_sum_func_list(all_fields, fields_list, 0) ||
1043
setup_sum_funcs(session, sum_funcs))
1048
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1050
session->set_proc_info("Sorting for order");
1051
if (create_sort_index(session, this, order,
1052
HA_POS_ERROR, HA_POS_ERROR, true))
1061
Optimize distinct when used on some of the tables
1062
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1063
In this case we can stop scanning t2 when we have found one t1.a
1066
if (exec_tmp_table1->distinct)
1068
table_map used_tables= session->used_tables;
1069
JoinTable *last_join_tab= join_tab+tables-1;
1072
if (used_tables & last_join_tab->table->map)
1074
last_join_tab->not_used_in_distinct=1;
1075
} while (last_join_tab-- != join_tab);
1076
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1077
if (order && skip_sort_order)
1079
/* Should always succeed */
1080
if (test_if_skip_sort_order(&join_tab[const_tables],
1081
order, unit->select_limit_cnt, 0,
1082
&join_tab[const_tables].table->
1083
keys_in_use_for_order_by))
1089
If this join belongs to an uncacheable subquery save
1092
if (select_lex->uncacheable.any() &&
1093
! is_top_level_join() &&
1094
init_save_join_tab())
1104
/* Even with zero matching rows, subqueries in the HAVING clause
1105
may need to be evaluated if there are aggregate functions in the query.
1107
if (setup_subquery_materialization())
1114
Restore values in temporary join.
1116
void Join::restore_tmp()
1118
memcpy(tmp_join, this, (size_t) sizeof(Join));
1123
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1124
select_lex->offset_limit->val_uint() :
1129
if (exec_tmp_table1)
1131
exec_tmp_table1->cursor->extra(HA_EXTRA_RESET_STATE);
1132
exec_tmp_table1->cursor->ha_delete_all_rows();
1133
exec_tmp_table1->free_io_cache();
1134
exec_tmp_table1->filesort_free_buffers();
1136
if (exec_tmp_table2)
1138
exec_tmp_table2->cursor->extra(HA_EXTRA_RESET_STATE);
1139
exec_tmp_table2->cursor->ha_delete_all_rows();
1140
exec_tmp_table2->free_io_cache();
1141
exec_tmp_table2->filesort_free_buffers();
1144
set_items_ref_array(items0);
1147
memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);
1152
/* Reset of sum functions */
1155
Item_sum *func, **func_ptr= sum_funcs;
1156
while ((func= *(func_ptr++)))
1164
@brief Save the original join layout
1166
@details Saves the original join layout so it can be reused in
1167
re-execution and for EXPLAIN.
1169
@return Operation status
1171
@retval 1 error occurred.
1173
bool Join::init_save_join_tab()
1175
if (!(tmp_join= (Join*)session->alloc(sizeof(Join))))
1178
error= 0; // Ensure that tmp_join.error= 0
1184
bool Join::save_join_tab()
1186
if (! join_tab_save && select_lex->master_unit()->uncacheable.any())
1188
if (!(join_tab_save= (JoinTable*)session->memdup((unsigned char*) join_tab,
1189
sizeof(JoinTable) * tables)))
1199
Note, that create_sort_index calls test_if_skip_sort_order and may
1200
finally replace sorting with index scan if there is a LIMIT clause in
1201
the query. It's never shown in EXPLAIN!
1204
When can we have here session->net.report_error not zero?
1208
List<Item> *columns_list= &fields_list;
1211
session->set_proc_info("executing");
1214
if (!tables_list && (tables || !select_lex->with_sum_func))
1216
/* Only test of functions */
1217
if (select_options & SELECT_DESCRIBE)
1219
optimizer::ExplainPlan planner(this,
1223
(zero_result_cause ? zero_result_cause : "No tables used"));
1224
planner.printPlan();
1228
result->send_fields(*columns_list);
1230
We have to test for 'conds' here as the WHERE may not be constant
1231
even if we don't have any tables for prepared statements or if
1232
conds uses something like 'rand()'.
1234
if (cond_value != Item::COND_FALSE &&
1235
(!conds || conds->val_int()) &&
1236
(!having || having->val_int()))
1238
if (do_send_rows && result->send_data(fields_list))
1242
error= (int) result->send_eof();
1243
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
1248
error= (int) result->send_eof();
1252
/* Single select (without union) always returns 0 or 1 row */
1253
session->limit_found_rows= send_records;
1254
session->examined_row_count= 0;
1258
Don't reset the found rows count if there're no tables as
1259
FOUND_ROWS() may be called. Never reset the examined row count here.
1260
It must be accumulated from all join iterations of all join parts.
1263
session->limit_found_rows= 0;
1265
if (zero_result_cause)
1267
(void) return_zero_rows(this, result, select_lex->leaf_tables,
1269
send_row_on_empty_set(),
1276
if (select_options & SELECT_DESCRIBE)
1279
Check if we managed to optimize ORDER BY away and don't use temporary
1280
table to resolve order_st BY: in that case, we only may need to do
1281
filesort for GROUP BY.
1283
if (!order && !no_order && (!skip_sort_order || !need_tmp))
1285
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
1287
simple_order= simple_group;
1290
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
1292
if (const_tables == tables
1293
|| ((simple_order || skip_sort_order)
1294
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
1298
optimizer::ExplainPlan planner(this,
1300
order != 0 && ! skip_sort_order,
1302
! tables ? "No tables used" : NULL);
1303
planner.printPlan();
1307
Join *curr_join= this;
1308
List<Item> *curr_all_fields= &all_fields;
1309
List<Item> *curr_fields_list= &fields_list;
1310
Table *curr_tmp_table= 0;
1312
Initialize examined rows here because the values from all join parts
1313
must be accumulated in examined_row_count. Hence every join
1314
iteration must count from zero.
1316
curr_join->examined_rows= 0;
1318
/* Create a tmp table if distinct or if the sort is too complicated */
1324
We are in a non cacheable sub query. Get the saved join structure
1326
(curr_join may have been modified during last exection and we need
1329
curr_join= tmp_join;
1331
curr_tmp_table= exec_tmp_table1;
1333
/* Copy data to the temporary table */
1334
session->set_proc_info("Copying to tmp table");
1335
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
1336
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1337
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1342
curr_tmp_table->cursor->info(HA_STATUS_VARIABLE);
1344
if (curr_join->having)
1345
curr_join->having= curr_join->tmp_having= 0; // Allready done
1347
/* Change sum_fields reference to calculated fields in tmp_table */
1348
curr_join->all_fields= *curr_all_fields;
1351
items1= items0 + all_fields.elements;
1352
if (sort_and_group || curr_tmp_table->group)
1354
if (change_to_use_tmp_fields(session, items1,
1355
tmp_fields_list1, tmp_all_fields1,
1356
fields_list.elements, all_fields))
1361
if (change_refs_to_tmp_fields(session, items1,
1362
tmp_fields_list1, tmp_all_fields1,
1363
fields_list.elements, all_fields))
1366
curr_join->tmp_all_fields1= tmp_all_fields1;
1367
curr_join->tmp_fields_list1= tmp_fields_list1;
1368
curr_join->items1= items1;
1370
curr_all_fields= &tmp_all_fields1;
1371
curr_fields_list= &tmp_fields_list1;
1372
curr_join->set_items_ref_array(items1);
1374
if (sort_and_group || curr_tmp_table->group)
1376
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
1377
+ curr_join->tmp_table_param.func_count;
1378
curr_join->tmp_table_param.sum_func_count= 0;
1379
curr_join->tmp_table_param.func_count= 0;
1383
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
1384
curr_join->tmp_table_param.func_count= 0;
1387
if (curr_tmp_table->group)
1388
{ // Already grouped
1389
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
1390
curr_join->order= curr_join->group_list; /* order by group */
1391
curr_join->group_list= 0;
1395
If we have different sort & group then we must sort the data by group
1396
and copy it to another tmp table
1397
This code is also used if we are using distinct something
1398
we haven't been able to store in the temporary table yet
1399
like SEC_TO_TIME(SUM(...)).
1402
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
1403
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
1404
{ /* Must copy to another table */
1405
/* Free first data from old join */
1406
curr_join->join_free();
1407
if (make_simple_join(curr_join, curr_tmp_table))
1409
calc_group_buffer(curr_join, group_list);
1410
count_field_types(select_lex, &curr_join->tmp_table_param,
1411
curr_join->tmp_all_fields1,
1412
curr_join->select_distinct && !curr_join->group_list);
1413
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
1414
- curr_join->tmp_fields_list1.elements;
1416
if (exec_tmp_table2)
1418
curr_tmp_table= exec_tmp_table2;
1422
/* group data to new table */
1425
If the access method is loose index scan then all MIN/MAX
1426
functions are precomputed, and should be treated as regular
1427
functions. See extended comment in Join::exec.
1429
if (curr_join->join_tab->is_using_loose_index_scan())
1430
curr_join->tmp_table_param.precomputed_group_by= true;
1432
if (!(curr_tmp_table=
1433
exec_tmp_table2= create_tmp_table(session,
1434
&curr_join->tmp_table_param,
1437
curr_join->select_distinct &&
1438
!curr_join->group_list,
1439
1, curr_join->select_options,
1446
curr_join->exec_tmp_table2= exec_tmp_table2;
1448
if (curr_join->group_list)
1450
session->set_proc_info("Creating sort index");
1451
if (curr_join->join_tab == join_tab && save_join_tab())
1455
if (create_sort_index(session, curr_join, curr_join->group_list,
1456
HA_POS_ERROR, HA_POS_ERROR, false) ||
1457
make_group_fields(this, curr_join))
1461
sortorder= curr_join->sortorder;
1464
session->set_proc_info("Copying to group table");
1466
if (curr_join != this)
1470
curr_join->sum_funcs= sum_funcs2;
1471
curr_join->sum_funcs_end= sum_funcs_end2;
1475
curr_join->alloc_func_list();
1476
sum_funcs2= curr_join->sum_funcs;
1477
sum_funcs_end2= curr_join->sum_funcs_end;
1480
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
1482
curr_join->group_list= 0;
1484
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
1485
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1487
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
1488
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1493
curr_join->join_tab->read_record.end_read_record();
1494
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1495
curr_join->join_tab[0].table= 0; // Table is freed
1497
// No sum funcs anymore
1500
items2= items1 + all_fields.elements;
1501
if (change_to_use_tmp_fields(session, items2,
1502
tmp_fields_list2, tmp_all_fields2,
1503
fields_list.elements, tmp_all_fields1))
1505
curr_join->tmp_fields_list2= tmp_fields_list2;
1506
curr_join->tmp_all_fields2= tmp_all_fields2;
1508
curr_fields_list= &curr_join->tmp_fields_list2;
1509
curr_all_fields= &curr_join->tmp_all_fields2;
1510
curr_join->set_items_ref_array(items2);
1511
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
1512
curr_join->tmp_table_param.sum_func_count= 0;
1514
if (curr_tmp_table->distinct)
1515
curr_join->select_distinct=0; /* Each row is unique */
1517
curr_join->join_free(); /* Free quick selects */
1518
if (curr_join->select_distinct && ! curr_join->group_list)
1520
session->set_proc_info("Removing duplicates");
1521
if (curr_join->tmp_having)
1522
curr_join->tmp_having->update_used_tables();
1524
if (remove_duplicates(curr_join, curr_tmp_table,
1525
*curr_fields_list, curr_join->tmp_having))
1528
curr_join->tmp_having=0;
1529
curr_join->select_distinct=0;
1531
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
1532
if (make_simple_join(curr_join, curr_tmp_table))
1534
calc_group_buffer(curr_join, curr_join->group_list);
1535
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
1539
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
1541
if (make_group_fields(this, curr_join))
1547
init_items_ref_array();
1548
items3= ref_pointer_array + (all_fields.elements*4);
1549
setup_copy_fields(session, &curr_join->tmp_table_param,
1550
items3, tmp_fields_list3, tmp_all_fields3,
1551
curr_fields_list->elements, *curr_all_fields);
1552
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
1553
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
1554
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
1555
curr_join->tmp_all_fields3= tmp_all_fields3;
1556
curr_join->tmp_fields_list3= tmp_fields_list3;
1560
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
1561
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
1562
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
1564
curr_fields_list= &tmp_fields_list3;
1565
curr_all_fields= &tmp_all_fields3;
1566
curr_join->set_items_ref_array(items3);
1568
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1570
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
1571
session->is_fatal_error)
1574
if (curr_join->group_list || curr_join->order)
1576
session->set_proc_info("Sorting result");
1577
/* If we have already done the group, add HAVING to sorted table */
1578
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
1580
// Some tables may have been const
1581
curr_join->tmp_having->update_used_tables();
1582
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];
1583
table_map used_tables= (curr_join->const_table_map |
1584
curr_table->table->map);
1586
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
1587
if (sort_table_cond)
1589
if (!curr_table->select)
1590
if (!(curr_table->select= new optimizer::SqlSelect))
1592
if (!curr_table->select->cond)
1593
curr_table->select->cond= sort_table_cond;
1594
else // This should never happen
1596
if (!(curr_table->select->cond=
1597
new Item_cond_and(curr_table->select->cond,
1601
Item_cond_and do not need fix_fields for execution, its parameters
1602
are fixed or do not need fix_fields, too
1604
curr_table->select->cond->quick_fix_field();
1606
curr_table->select_cond= curr_table->select->cond;
1607
curr_table->select_cond->top_level_item();
1608
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
1615
curr_join->select_limit= HA_POS_ERROR;
1619
We can abort sorting after session->select_limit rows if we there is no
1620
WHERE clause for any tables after the sorted one.
1622
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
1623
JoinTable *end_table= &curr_join->join_tab[curr_join->tables];
1624
for (; curr_table < end_table ; curr_table++)
1627
table->keyuse is set in the case there was an original WHERE clause
1628
on the table that was optimized away.
1630
if (curr_table->select_cond ||
1631
(curr_table->keyuse && !curr_table->first_inner))
1633
/* We have to sort all rows */
1634
curr_join->select_limit= HA_POS_ERROR;
1639
if (curr_join->join_tab == join_tab && save_join_tab())
1642
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
1643
chose FILESORT to be faster than INDEX SCAN or there is no
1644
suitable index present.
1645
Note, that create_sort_index calls test_if_skip_sort_order and may
1646
finally replace sorting with index scan if there is a LIMIT clause in
1647
the query. XXX: it's never shown in EXPLAIN!
1648
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
1650
if (create_sort_index(session, curr_join,
1651
curr_join->group_list ?
1652
curr_join->group_list : curr_join->order,
1653
curr_join->select_limit,
1654
(select_options & OPTION_FOUND_ROWS ?
1655
HA_POS_ERROR : unit->select_limit_cnt),
1656
curr_join->group_list ? true : false))
1659
sortorder= curr_join->sortorder;
1660
if (curr_join->const_tables != curr_join->tables &&
1661
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
1664
If no IO cache exists for the first table then we are using an
1665
INDEX SCAN and no filesort. Thus we should not remove the sorted
1666
attribute on the INDEX SCAN.
1672
/* XXX: When can we have here session->is_error() not zero? */
1673
if (session->is_error())
1675
error= session->is_error();
1678
curr_join->having= curr_join->tmp_having;
1679
curr_join->fields= curr_fields_list;
1681
session->set_proc_info("Sending data");
1682
result->send_fields(*curr_fields_list);
1683
error= do_select(curr_join, curr_fields_list, NULL);
1684
session->limit_found_rows= curr_join->send_records;
1686
/* Accumulate the counts from all join iterations of all join parts. */
1687
session->examined_row_count+= curr_join->examined_rows;
1690
With EXPLAIN EXTENDED we have to restore original ref_array
1691
for a derived table which is always materialized.
1692
Otherwise we would not be able to print the query correctly.
1694
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
1695
set_items_ref_array(items0);
1704
Return error that hold Join.
1708
select_lex->join= 0;
1712
if (join_tab != tmp_join->join_tab)
1714
JoinTable *tab, *end;
1715
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
1718
tmp_join->tmp_join= 0;
1719
tmp_table_param.copy_field=0;
1720
return(tmp_join->destroy());
1725
exec_tmp_table1= NULL;
1726
exec_tmp_table2= NULL;
1728
delete_dynamic(&keyuse);
1734
Setup for execution all subqueries of a query, for which the optimizer
1735
chose hash semi-join.
1737
@details Iterate over all subqueries of the query, and if they are under an
1738
IN predicate, and the optimizer chose to compute it via hash semi-join:
1739
- try to initialize all data structures needed for the materialized execution
1740
of the IN predicate,
1741
- if this fails, then perform the IN=>EXISTS transformation which was
1742
previously blocked during Join::prepare.
1744
This method is part of the "code generation" query processing phase.
1746
This phase must be called after substitute_for_best_equal_field() because
1747
that function may replace items with other items from a multiple equality,
1748
and we need to reference the correct items in the index access method of the
1751
@return Operation status
1752
@retval false success.
1753
@retval true error occurred.
1755
bool Join::setup_subquery_materialization()
1757
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1758
un= un->next_unit())
1760
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
1762
Item_subselect *subquery_predicate= sl->master_unit()->item;
1763
if (subquery_predicate &&
1764
subquery_predicate->substype() == Item_subselect::IN_SUBS)
1766
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
1767
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
1768
in_subs->setup_engine())
1777
Partially cleanup Join after it has executed: close index or rnd read
1778
(table cursors), free quick selects.
1780
This function is called in the end of execution of a Join, before the used
1781
tables are unlocked and closed.
1783
For a join that is resolved using a temporary table, the first sweep is
1784
performed against actual tables and an intermediate result is inserted
1785
into the temprorary table.
1786
The last sweep is performed against the temporary table. Therefore,
1787
the base tables and associated buffers used to fill the temporary table
1788
are no longer needed, and this function is called to free them.
1790
For a join that is performed without a temporary table, this function
1791
is called after all rows are sent, but before EOF packet is sent.
1793
For a simple SELECT with no subqueries this function performs a full
1794
cleanup of the Join and calls unlockReadTables to free used base
1797
If a Join is executed for a subquery or if it has a subquery, we can't
1798
do the full cleanup and need to do a partial cleanup only.
1799
- If a Join is not the top level join, we must not unlock the tables
1800
because the outer select may not have been evaluated yet, and we
1801
can't unlock only selected tables of a query.
1802
- Additionally, if this Join corresponds to a correlated subquery, we
1803
should not free quick selects and join buffers because they will be
1804
needed for the next execution of the correlated subquery.
1805
- However, if this is a Join for a [sub]select, which is not
1806
a correlated subquery itself, but has subqueries, we can free it
1807
fully and also free Joins of all its subqueries. The exception
1808
is a subquery in SELECT list, e.g: @n
1809
SELECT a, (select cmax(b) from t1) group by c @n
1810
This subquery will not be evaluated at first sweep and its value will
1811
not be inserted into the temporary table. Instead, it's evaluated
1812
when selecting from the temporary table. Therefore, it can't be freed
1813
here even though it's not correlated.
1816
Unlock tables even if the join isn't top level select in the tree
1818
void Join::join_free()
1820
Select_Lex_Unit *tmp_unit;
1823
Optimization: if not EXPLAIN and we are done with the Join,
1826
bool full= (select_lex->uncacheable.none() && ! session->lex->describe);
1827
bool can_unlock= full;
1831
for (tmp_unit= select_lex->first_inner_unit();
1833
tmp_unit= tmp_unit->next_unit())
1834
for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
1836
Item_subselect *subselect= sl->master_unit()->item;
1837
bool full_local= full && (!subselect || subselect->is_evaluated());
1839
If this join is evaluated, we can fully clean it up and clean up all
1840
its underlying joins even if they are correlated -- they will not be
1841
used any more anyway.
1842
If this join is not yet evaluated, we still must clean it up to
1843
close its table cursors -- it may never get evaluated, as in case of
1844
... HAVING false OR a IN (SELECT ...))
1845
but all table cursors must be closed before the unlock.
1847
sl->cleanup_all_joins(full_local);
1848
/* Can't unlock if at least one Join is still needed */
1849
can_unlock= can_unlock && full_local;
1853
We are not using tables anymore
1854
Unlock all tables. We may be in an INSERT .... SELECT statement.
1856
if (can_unlock && lock && session->lock &&
1857
!(select_options & SELECT_NO_UNLOCK) &&
1858
!select_lex->subquery_in_having &&
1859
(select_lex == (session->lex->unit.fake_select_lex ?
1860
session->lex->unit.fake_select_lex : &session->lex->select_lex)))
1863
TODO: unlock tables even if the join isn't top level select in the
1866
session->unlockReadTables(lock); // Don't free join->lock
1875
Free resources of given join.
1877
@param fill true if we should free all resources, call with full==1
1878
should be last, before it this function can be called with
1882
With subquery this function definitely will be called several times,
1883
but even for simple query it can be called several times.
1885
void Join::cleanup(bool full)
1889
JoinTable *tab,*end;
1891
Only a sorted table may be cached. This sorted table is always the
1892
first non const table in join->table
1894
if (tables > const_tables) // Test for not-const tables
1896
table[const_tables]->free_io_cache();
1897
table[const_tables]->filesort_free_buffers(full);
1902
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1908
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1911
tab->table->cursor->ha_index_or_rnd_end();
1916
We are not using tables anymore
1917
Unlock all tables. We may be in an INSERT .... SELECT statement.
1922
tmp_table_param.copy_field= 0;
1923
group_fields.delete_elements();
1925
We can't call delete_elements() on copy_funcs as this will cause
1926
problems in free_elements() as some of the elements are then deleted.
1928
tmp_table_param.copy_funcs.empty();
1930
If we have tmp_join and 'this' Join is not tmp_join and
1931
tmp_table_param.copy_field's of them are equal then we have to remove
1932
pointer to tmp_table_param.copy_field from tmp_join, because it qill
1933
be removed in tmp_table_param.cleanup().
1937
tmp_join->tmp_table_param.copy_field ==
1938
tmp_table_param.copy_field)
1940
tmp_join->tmp_table_param.copy_field=
1941
tmp_join->tmp_table_param.save_copy_field= 0;
1943
tmp_table_param.cleanup();
1949
used only in Join::clear
1951
static void clear_tables(Join *join)
1954
must clear only the non-const tables, as const tables
1955
are not re-calculated.
1957
for (uint32_t i= join->const_tables; i < join->tables; i++)
1958
join->table[i]->mark_as_null_row(); // All fields are NULL
1962
Make an array of pointers to sum_functions to speed up
1963
sum_func calculation.
1970
bool Join::alloc_func_list()
1972
uint32_t func_count, group_parts;
1974
func_count= tmp_table_param.sum_func_count;
1976
If we are using rollup, we need a copy of the summary functions for
1979
if (rollup.state != ROLLUP::STATE_NONE)
1980
func_count*= (send_group_parts+1);
1982
group_parts= send_group_parts;
1984
If distinct, reserve memory for possible
1985
disctinct->group_by optimization
1987
if (select_distinct)
1989
group_parts+= fields_list.elements;
1991
If the order_st clause is specified then it's possible that
1992
it also will be optimized, so reserve space for it too
1997
for (ord= order; ord; ord= ord->next)
2002
/* This must use calloc() as rollup_make_fields depends on this */
2003
sum_funcs= (Item_sum**) session->calloc(sizeof(Item_sum**) * (func_count+1) +
2004
sizeof(Item_sum***) * (group_parts+1));
2005
sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
2006
return(sum_funcs == 0);
2010
Initialize 'sum_funcs' array with all Item_sum objects.
2012
@param field_list All items
2013
@param send_fields Items in select list
2014
@param before_group_by Set to 1 if this is called before GROUP BY handling
2015
@param recompute Set to true if sum_funcs must be recomputed
2022
bool Join::make_sum_func_list(List<Item> &field_list,
2023
List<Item> &send_fields,
2024
bool before_group_by,
2027
List_iterator_fast<Item> it(field_list);
2031
if (*sum_funcs && !recompute)
2032
return(false); /* We have already initialized sum_funcs. */
2037
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2038
(!((Item_sum*) item)->depended_from() ||
2039
((Item_sum *)item)->depended_from() == select_lex))
2040
*func++= (Item_sum*) item;
2042
if (before_group_by && rollup.state == ROLLUP::STATE_INITED)
2044
rollup.state= ROLLUP::STATE_READY;
2045
if (rollup_make_fields(field_list, send_fields, &func))
2046
return(true); // Should never happen
2048
else if (rollup.state == ROLLUP::STATE_NONE)
2050
for (uint32_t i=0 ; i <= send_group_parts ;i++)
2051
sum_funcs_end[i]= func;
2053
else if (rollup.state == ROLLUP::STATE_READY)
2054
return(false); // Don't put end marker
2055
*func=0; // End marker
2059
/** Allocate memory needed for other rollup functions. */
2060
bool Join::rollup_init()
2065
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2066
rollup.state= ROLLUP::STATE_INITED;
2069
Create pointers to the different sum function groups
2070
These are updated by rollup_make_fields()
2072
tmp_table_param.group_parts= send_group_parts;
2074
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
2076
sizeof(List<Item>) +
2077
ref_pointer_array_size)
2078
* send_group_parts )))
2081
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
2082
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
2083
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
2086
Prepare space for field list for the different levels
2087
These will be filled up in rollup_make_fields()
2089
for (i= 0 ; i < send_group_parts ; i++)
2091
rollup.null_items[i]= new (session->mem_root) Item_null_result();
2092
List<Item> *rollup_fields= &rollup.fields[i];
2093
rollup_fields->empty();
2094
rollup.ref_pointer_arrays[i]= ref_array;
2095
ref_array+= all_fields.elements;
2097
for (i= 0 ; i < send_group_parts; i++)
2099
for (j=0 ; j < fields_list.elements ; j++)
2100
rollup.fields[i].push_back(rollup.null_items[i]);
2102
List_iterator<Item> it(all_fields);
2104
while ((item= it++))
2107
bool found_in_group= 0;
2109
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2111
if (*group_tmp->item == item)
2113
item->maybe_null= 1;
2115
if (item->const_item())
2118
For ROLLUP queries each constant item referenced in GROUP BY list
2119
is wrapped up into an Item_func object yielding the same value
2120
as the constant item. The objects of the wrapper class are never
2121
considered as constant items and besides they inherit all
2122
properties of the Item_result_field class.
2123
This wrapping allows us to ensure writing constant items
2124
into temporary tables whenever the result of the ROLLUP
2125
operation has to be written into a temporary table, e.g. when
2126
ROLLUP is used together with DISTINCT in the SELECT list.
2127
Usually when creating temporary tables for a intermidiate
2128
result we do not include fields for constant expressions.
2130
Item* new_item= new Item_func_rollup_const(item);
2133
new_item->fix_fields(session, (Item **) 0);
2134
session->change_item_tree(it.ref(), new_item);
2135
for (Order *tmp= group_tmp; tmp; tmp= tmp->next)
2137
if (*tmp->item == item)
2138
session->change_item_tree(tmp->item, new_item);
2143
if (item->type() == Item::FUNC_ITEM && !found_in_group)
2145
bool changed= false;
2146
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
2149
We have to prevent creation of a field in a temporary table for
2150
an expression that contains GROUP BY attributes.
2151
Marking the expression item as 'with_sum_func' will ensure this.
2154
item->with_sum_func= 1;
2161
Fill up rollup structures with pointers to fields to use.
2163
Creates copies of item_sum items for each sum level.
2165
@param fields_arg List of all fields (hidden and real ones)
2166
@param sel_fields Pointer to selected fields
2167
@param func Store here a pointer to all fields
2171
In this case func is pointing to next not used element.
2175
bool Join::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2177
List_iterator_fast<Item> it(fields_arg);
2178
Item *first_field= sel_fields.head();
2182
Create field lists for the different levels
2184
The idea here is to have a separate field list for each rollup level to
2185
avoid all runtime checks of which columns should be NULL.
2187
The list is stored in reverse order to get sum function in such an order
2188
in func that it makes it easy to reset them with init_sum_functions()
2190
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2192
rollup.fields[0] will contain list where a,b,c is NULL
2193
rollup.fields[1] will contain list where b,c is NULL
2195
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
2197
sum_funcs_end[0] points to all sum functions
2198
sum_funcs_end[1] points to all sum functions, except grand totals
2202
for (level=0 ; level < send_group_parts ; level++)
2205
uint32_t pos= send_group_parts - level -1;
2206
bool real_fields= 0;
2208
List_iterator<Item> new_it(rollup.fields[pos]);
2209
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
2212
/* Point to first hidden field */
2213
Item **ref_array= ref_array_start + fields_arg.elements-1;
2215
/* Remember where the sum functions ends for the previous level */
2216
sum_funcs_end[pos+1]= *func;
2218
/* Find the start of the group for this level */
2219
for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
2223
while ((item= it++))
2225
if (item == first_field)
2227
real_fields= 1; // End of hidden fields
2228
ref_array= ref_array_start;
2231
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2232
(!((Item_sum*) item)->depended_from() ||
2233
((Item_sum *)item)->depended_from() == select_lex))
2237
This is a top level summary function that must be replaced with
2238
a sum function that is reset for this level.
2240
NOTE: This code creates an object which is not that nice in a
2241
sub select. Fortunately it's not common to have rollup in
2244
item= item->copy_or_same(session);
2245
((Item_sum*) item)->make_unique();
2246
*(*func)= (Item_sum*) item;
2251
/* Check if this is something that is part of this group by */
2253
for (group_tmp= start_group, i= pos ;
2254
group_tmp ; group_tmp= group_tmp->next, i++)
2256
if (*group_tmp->item == item)
2259
This is an element that is used by the GROUP BY and should be
2260
set to NULL in this level
2262
Item_null_result *null_item= new (session->mem_root) Item_null_result();
2265
item->maybe_null= 1; // Value will be null sometimes
2266
null_item->result_field= item->get_tmp_table_field();
2275
(void) new_it++; // Point to next item
2276
new_it.replace(item); // Replace previous
2283
sum_funcs_end[0]= *func; // Point to last function
2288
Send all rollup levels higher than the current one to the client.
2292
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2295
@param idx Level we are on:
2296
- 0 = Total sum level
2297
- 1 = First group changed (a)
2298
- 2 = Second group changed (a,b)
2303
1 If send_data_failed()
2305
int Join::rollup_send_data(uint32_t idx)
2308
for (i= send_group_parts ; i-- > idx ; )
2310
/* Get reference pointers to sum functions in place */
2311
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2312
ref_pointer_array_size);
2313
if ((!having || having->val_int()))
2315
if (send_records < unit->select_limit_cnt && do_send_rows &&
2316
result->send_data(rollup.fields[i]))
2321
/* Restore ref_pointer_array */
2322
set_items_ref_array(current_ref_pointer_array);
2327
Write all rollup levels higher than the current one to a temp table.
2331
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
2334
@param idx Level we are on:
2335
- 0 = Total sum level
2336
- 1 = First group changed (a)
2337
- 2 = Second group changed (a,b)
2338
@param table reference to temp table
2343
1 if write_data_failed()
2345
int Join::rollup_write_data(uint32_t idx, Table *table_arg)
2348
for (i= send_group_parts ; i-- > idx ; )
2350
/* Get reference pointers to sum functions in place */
2351
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2352
ref_pointer_array_size);
2353
if ((!having || having->val_int()))
2357
List_iterator_fast<Item> it(rollup.fields[i]);
2358
while ((item= it++))
2360
if (item->type() == Item::NULL_ITEM && item->is_result_field())
2361
item->save_in_result_field(1);
2363
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2364
if ((write_error= table_arg->cursor->insertRecord(table_arg->getInsertRecord())))
2366
my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2371
/* Restore ref_pointer_array */
2372
set_items_ref_array(current_ref_pointer_array);
2377
clear results if there are not rows found for group
2378
(end_send_group/end_write_group)
2383
copy_fields(&tmp_table_param);
2387
Item_sum *func, **func_ptr= sum_funcs;
2388
while ((func= *(func_ptr++)))
2394
change select_result object of Join.
2396
@param res new select_result object
2403
bool Join::change_result(select_result *res)
2406
if (result->prepare(fields_list, select_lex->master_unit()))
2414
Cache constant expressions in WHERE, HAVING, ON conditions.
2417
void Join::cache_const_exprs()
2419
bool cache_flag= false;
2420
bool *analyzer_arg= &cache_flag;
2422
/* No need in cache if all tables are constant. */
2423
if (const_tables == tables)
2427
conds->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2428
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2431
having->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2432
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2434
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
2436
if (*tab->on_expr_ref)
2439
(*tab->on_expr_ref)->compile(&Item::cache_const_expr_analyzer,
2440
(unsigned char **)&analyzer_arg,
2441
&Item::cache_const_expr_transformer,
2442
(unsigned char *)&cache_flag);
2450
Process one record of the nested loop join.
2454
This function will evaluate parts of WHERE/ON clauses that are
2455
applicable to the partial record on hand and in case of success
2456
submit this record to the next level of the nested loop.
2458
enum_nested_loop_state evaluate_join_record(Join *join, JoinTable *join_tab, int error)
2460
bool not_used_in_distinct= join_tab->not_used_in_distinct;
2461
ha_rows found_records= join->found_records;
2462
COND *select_cond= join_tab->select_cond;
2464
if (error > 0 || (join->session->is_error())) // Fatal error
2465
return NESTED_LOOP_ERROR;
2467
return NESTED_LOOP_NO_MORE_ROWS;
2468
if (join->session->getKilled()) // Aborted by user
2470
join->session->send_kill_message();
2471
return NESTED_LOOP_KILLED;
2473
if (!select_cond || select_cond->val_int())
2476
There is no select condition or the attached pushed down
2477
condition is true => a match is found.
2480
while (join_tab->first_unmatched && found)
2483
The while condition is always false if join_tab is not
2484
the last inner join table of an outer join operation.
2486
JoinTable *first_unmatched= join_tab->first_unmatched;
2488
Mark that a match for current outer table is found.
2489
This activates push down conditional predicates attached
2490
to the all inner tables of the outer join.
2492
first_unmatched->found= 1;
2493
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2495
if (tab->table->reginfo.not_exists_optimize)
2496
return NESTED_LOOP_NO_MORE_ROWS;
2497
/* Check all predicates that has just been activated. */
2499
Actually all predicates non-guarded by first_unmatched->found
2500
will be re-evaluated again. It could be fixed, but, probably,
2501
it's not worth doing now.
2503
if (tab->select_cond && !tab->select_cond->val_int())
2505
/* The condition attached to table tab is false */
2506
if (tab == join_tab)
2511
Set a return point if rejected predicate is attached
2512
not to the last table of the current nest level.
2514
join->return_tab= tab;
2515
return NESTED_LOOP_OK;
2520
Check whether join_tab is not the last inner table
2521
for another embedding outer join.
2523
if ((first_unmatched= first_unmatched->first_upper) &&
2524
first_unmatched->last_inner != join_tab)
2526
join_tab->first_unmatched= first_unmatched;
2529
JoinTable *return_tab= join->return_tab;
2530
join_tab->found_match= true;
2533
It was not just a return to lower loop level when one
2534
of the newly activated predicates is evaluated as false
2535
(See above join->return_tab= tab).
2537
join->examined_rows++;
2538
join->session->row_count++;
2542
enum enum_nested_loop_state rc;
2543
/* A match from join_tab is found for the current partial join. */
2544
rc= (*join_tab->next_select)(join, join_tab+1, 0);
2545
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2547
if (return_tab < join->return_tab)
2548
join->return_tab= return_tab;
2550
if (join->return_tab < join_tab)
2551
return NESTED_LOOP_OK;
2553
Test if this was a SELECT DISTINCT query on a table that
2554
was not in the field list; In this case we can abort if
2555
we found a row, as no new rows can be added to the result.
2557
if (not_used_in_distinct && found_records != join->found_records)
2558
return NESTED_LOOP_NO_MORE_ROWS;
2561
join_tab->read_record.cursor->unlock_row();
2566
The condition pushed down to the table join_tab rejects all rows
2567
with the beginning coinciding with the current partial join.
2569
join->examined_rows++;
2570
join->session->row_count++;
2571
join_tab->read_record.cursor->unlock_row();
2573
return NESTED_LOOP_OK;
2578
Construct a NULL complimented partial join record and feed it to the next
2579
level of the nested loop. This function is used in case we have
2580
an OUTER join and no matching record was found.
2582
enum_nested_loop_state evaluate_null_complemented_join_record(Join *join, JoinTable *join_tab)
2585
The table join_tab is the first inner table of a outer join operation
2586
and no matches has been found for the current outer row.
2588
JoinTable *last_inner_tab= join_tab->last_inner;
2589
/* Cache variables for faster loop */
2591
for ( ; join_tab <= last_inner_tab ; join_tab++)
2593
/* Change the the values of guard predicate variables. */
2595
join_tab->not_null_compl= 0;
2596
/* The outer row is complemented by nulls for each inner tables */
2597
join_tab->table->restoreRecordAsDefault(); // Make empty record
2598
join_tab->table->mark_as_null_row(); // For group by without error
2599
select_cond= join_tab->select_cond;
2600
/* Check all attached conditions for inner table rows. */
2601
if (select_cond && !select_cond->val_int())
2602
return NESTED_LOOP_OK;
2606
The row complemented by nulls might be the first row
2607
of embedding outer joins.
2608
If so, perform the same actions as in the code
2609
for the first regular outer join row above.
2613
JoinTable *first_unmatched= join_tab->first_unmatched;
2614
if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
2616
join_tab->first_unmatched= first_unmatched;
2617
if (! first_unmatched)
2619
first_unmatched->found= 1;
2620
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2622
if (tab->select_cond && !tab->select_cond->val_int())
2624
join->return_tab= tab;
2625
return NESTED_LOOP_OK;
2630
The row complemented by nulls satisfies all conditions
2631
attached to inner tables.
2632
Send the row complemented by nulls to be joined with the
2635
return (*join_tab->next_select)(join, join_tab+1, 0);
2638
enum_nested_loop_state flush_cached_records(Join *join, JoinTable *join_tab, bool skip_last)
2640
enum_nested_loop_state rc= NESTED_LOOP_OK;
2644
join_tab->table->null_row= 0;
2645
if (!join_tab->cache.records)
2647
return NESTED_LOOP_OK; /* Nothing to do */
2652
(void) join_tab->cache.store_record_in_cache(); // Must save this for later
2656
if (join_tab->use_quick == 2)
2658
if (join_tab->select->quick)
2659
{ /* Used quick select last. reset it */
2660
delete join_tab->select->quick;
2661
join_tab->select->quick=0;
2664
/* read through all records */
2665
if ((error=join_init_read_record(join_tab)))
2667
join_tab->cache.reset_cache_write();
2668
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2671
for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)
2673
tmp->status=tmp->table->status;
2674
tmp->table->status=0;
2677
info= &join_tab->read_record;
2680
if (join->session->getKilled())
2682
join->session->send_kill_message();
2683
return NESTED_LOOP_KILLED;
2685
optimizer::SqlSelect *select= join_tab->select;
2686
if (rc == NESTED_LOOP_OK &&
2687
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2690
join_tab->cache.reset_cache_read();
2691
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2693
join_tab->readCachedRecord();
2694
if (!select || !select->skip_record())
2698
rc= (join_tab->next_select)(join,join_tab+1,0);
2699
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2701
join_tab->cache.reset_cache_write();
2706
return NESTED_LOOP_ERROR;
2710
} while (!(error=info->read_record(info)));
2713
join_tab->readCachedRecord(); // Restore current record
2714
join_tab->cache.reset_cache_write();
2715
if (error > 0) // Fatal error
2716
return NESTED_LOOP_ERROR;
2717
for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2718
tmp2->table->status=tmp2->status;
2719
return NESTED_LOOP_OK;
2722
/*****************************************************************************
2724
Functions that end one nested loop iteration. Different functions
2725
are used to support GROUP BY clause and to redirect records
2726
to a table (e.g. in case of SELECT into a temporary table) or to the
2730
NESTED_LOOP_OK - the record has been successfully handled
2731
NESTED_LOOP_ERROR - a fatal error (like table corruption)
2733
NESTED_LOOP_KILLED - thread shutdown was requested while processing
2735
NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;
2736
additionally, the nested loop produced the
2737
number of rows specified in the LIMIT clause
2739
NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
2740
additionally, there is a cursor and the nested
2741
loop algorithm produced the number of rows
2742
that is specified for current cursor fetch
2744
All return values except NESTED_LOOP_OK abort the nested loop.
2745
*****************************************************************************/
2746
enum_nested_loop_state end_send(Join *join, JoinTable *, bool end_of_records)
2748
if (! end_of_records)
2751
if (join->having && join->having->val_int() == 0)
2752
return NESTED_LOOP_OK; // Didn't match having
2754
if (join->do_send_rows)
2755
error=join->result->send_data(*join->fields);
2757
return NESTED_LOOP_ERROR;
2758
if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2760
if (join->select_options & OPTION_FOUND_ROWS)
2762
JoinTable *jt=join->join_tab;
2763
if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2764
&& !join->send_group_parts && !join->having && !jt->select_cond &&
2765
!(jt->select && jt->select->quick) &&
2766
(jt->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
2769
/* Join over all rows in table; Return number of found rows */
2770
Table *table= jt->table;
2772
join->select_options^= OPTION_FOUND_ROWS;
2773
if (table->sort.record_pointers ||
2774
(table->sort.io_cache && my_b_inited(table->sort.io_cache)))
2776
/* Using filesort */
2777
join->send_records= table->sort.found_records;
2781
table->cursor->info(HA_STATUS_VARIABLE);
2782
join->send_records= table->cursor->stats.records;
2787
join->do_send_rows= 0;
2788
if (join->unit->fake_select_lex)
2789
join->unit->fake_select_lex->select_limit= 0;
2790
return NESTED_LOOP_OK;
2793
return NESTED_LOOP_QUERY_LIMIT; // Abort nicely
2795
else if (join->send_records >= join->fetch_limit)
2798
There is a server side cursor and all rows for
2799
this fetch request are sent.
2801
return NESTED_LOOP_CURSOR_LIMIT;
2805
return NESTED_LOOP_OK;
2808
enum_nested_loop_state end_write(Join *join, JoinTable *, bool end_of_records)
2810
Table *table= join->tmp_table;
2812
if (join->session->getKilled()) // Aborted by user
2814
join->session->send_kill_message();
2815
return NESTED_LOOP_KILLED;
2817
if (!end_of_records)
2819
copy_fields(&join->tmp_table_param);
2820
if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
2821
return NESTED_LOOP_ERROR;
2822
if (!join->having || join->having->val_int())
2825
join->found_records++;
2826
if ((error=table->cursor->insertRecord(table->getInsertRecord())))
2828
if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))
2830
return NESTED_LOOP_OK;
2833
my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2834
return NESTED_LOOP_ERROR; // Table is_full error
2836
if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
2838
if (!(join->select_options & OPTION_FOUND_ROWS))
2839
return NESTED_LOOP_QUERY_LIMIT;
2840
join->do_send_rows= 0;
2841
join->unit->select_limit_cnt= HA_POS_ERROR;
2842
return NESTED_LOOP_OK;
2847
return NESTED_LOOP_OK;
2850
/** Group by searching after group record and updating it if possible. */
2851
enum_nested_loop_state end_update(Join *join, JoinTable *, bool end_of_records)
2853
Table *table= join->tmp_table;
2858
return NESTED_LOOP_OK;
2859
if (join->session->getKilled()) // Aborted by user
2861
join->session->send_kill_message();
2862
return NESTED_LOOP_KILLED;
2865
join->found_records++;
2866
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2867
/* Make a key of group index */
2868
for (group=table->group ; group ; group=group->next)
2870
Item *item= *group->item;
2871
item->save_org_in_field(group->field);
2872
/* Store in the used key if the field was 0 */
2873
if (item->maybe_null)
2874
group->buff[-1]= (char) group->field->is_null();
2876
if (!table->cursor->index_read_map(table->getUpdateRecord(),
2877
join->tmp_table_param.group_buff,
2880
{ /* Update old record */
2881
table->restoreRecord();
2882
update_tmptable_sum_func(join->sum_funcs,table);
2883
if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
2884
table->getInsertRecord())))
2886
table->print_error(error,MYF(0));
2887
return NESTED_LOOP_ERROR;
2889
return NESTED_LOOP_OK;
2893
Copy null bits from group key to table
2894
We can't copy all data as the key may have different format
2895
as the row data (for example as with VARCHAR keys)
2897
KeyPartInfo *key_part;
2898
for (group=table->group,key_part=table->key_info[0].key_part;
2900
group=group->next,key_part++)
2902
if (key_part->null_bit)
2903
memcpy(table->getInsertRecord()+key_part->offset, group->buff, 1);
2905
init_tmptable_sum_functions(join->sum_funcs);
2906
if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
2907
return NESTED_LOOP_ERROR;
2908
if ((error=table->cursor->insertRecord(table->getInsertRecord())))
2910
my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2911
return NESTED_LOOP_ERROR; // Table is_full error
2913
join->send_records++;
2914
return NESTED_LOOP_OK;
2917
/** Like end_update, but this is done with unique constraints instead of keys. */
2918
enum_nested_loop_state end_unique_update(Join *join, JoinTable *, bool end_of_records)
2920
Table *table= join->tmp_table;
2924
return NESTED_LOOP_OK;
2925
if (join->session->getKilled()) // Aborted by user
2927
join->session->send_kill_message();
2928
return NESTED_LOOP_KILLED;
2931
init_tmptable_sum_functions(join->sum_funcs);
2932
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2933
if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
2934
return NESTED_LOOP_ERROR;
2936
if (!(error= table->cursor->insertRecord(table->getInsertRecord())))
2937
join->send_records++; // New group
2940
if ((int) table->get_dup_key(error) < 0)
2942
table->print_error(error,MYF(0));
2943
return NESTED_LOOP_ERROR;
2945
if (table->cursor->rnd_pos(table->getUpdateRecord(),table->cursor->dup_ref))
2947
table->print_error(error,MYF(0));
2948
return NESTED_LOOP_ERROR;
2950
table->restoreRecord();
2951
update_tmptable_sum_func(join->sum_funcs,table);
2952
if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
2953
table->getInsertRecord())))
2955
table->print_error(error,MYF(0));
2956
return NESTED_LOOP_ERROR;
2959
return NESTED_LOOP_OK;
2963
allocate group fields or take prepared (cached).
2965
@param main_join join of current select
2966
@param curr_join current join (join of current select or temporary copy
2974
static bool make_group_fields(Join *main_join, Join *curr_join)
2976
if (main_join->group_fields_cache.elements)
2978
curr_join->group_fields= main_join->group_fields_cache;
2979
curr_join->sort_and_group= 1;
2983
if (alloc_group_fields(curr_join, curr_join->group_list))
2985
main_join->group_fields_cache= curr_join->group_fields;
2991
calc how big buffer we need for comparing group entries.
2993
static void calc_group_buffer(Join *join, Order *group)
2995
uint32_t key_length=0, parts=0, null_parts=0;
2999
for (; group ; group=group->next)
3001
Item *group_item= *group->item;
3002
Field *field= group_item->get_tmp_table_field();
3005
enum_field_types type;
3006
if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
3007
key_length+=MAX_BLOB_WIDTH; // Can't be used as a key
3008
else if (type == DRIZZLE_TYPE_VARCHAR)
3009
key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
3011
key_length+= field->pack_length();
3015
switch (group_item->result_type()) {
3017
key_length+= sizeof(double);
3021
key_length+= sizeof(int64_t);
3024
case DECIMAL_RESULT:
3025
key_length+= my_decimal_get_binary_size(group_item->max_length -
3026
(group_item->decimals ? 1 : 0),
3027
group_item->decimals);
3032
enum enum_field_types type= group_item->field_type();
3034
As items represented as DATE/TIME fields in the group buffer
3035
have STRING_RESULT result type, we increase the length
3036
by 8 as maximum pack length of such fields.
3038
if (type == DRIZZLE_TYPE_DATE ||
3039
type == DRIZZLE_TYPE_DATETIME ||
3040
type == DRIZZLE_TYPE_TIMESTAMP)
3047
Group strings are taken as varstrings and require an length field.
3048
A field is not yet created by create_tmp_field()
3049
and the sizes should match up.
3051
key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3057
/* This case should never be choosen */
3059
my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
3065
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 *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->getKilled()) // 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 *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 *remove_constants(Join *join,Order *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 *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
// @note c_str() is not likely to be valid here if dtrace expects it to
5885
// exist for any period of time.
5886
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->getQueryString()->c_str(), join->session->thread_id);
5887
bool res= choose_plan(join, all_table_map & ~join->const_table_map);
5888
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);
5894
join->copyPartialPlanIntoOptimalPlan(join->const_tables);
5895
join->best_read= 1.0;
5897
/* Generate an execution plan from the found optimal join order. */
5898
return (join->session->getKilled() || get_best_combination(join));
5902
Assign each nested join structure a bit in the nested join bitset.
5904
Assign each nested join structure (except "confluent" ones - those that
5905
embed only one element) a bit in the nested join bitset.
5907
@param join Join being processed
5908
@param join_list List of tables
5909
@param first_unused Number of first unused bit in the nest joing bitset before the
5913
This function is called after simplify_joins(), when there are no
5914
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
5915
we will not run out of bits in the nested join bitset.
5918
First unused bit in the nest join bitset after the call.
5920
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
5922
List_iterator<TableList> li(*join_list);
5924
while ((table= li++))
5926
nested_join_st *nested_join;
5927
if ((nested_join= table->getNestedJoin()))
5930
It is guaranteed by simplify_joins() function that a nested join
5931
that has only one child is either
5932
- a single-table view (the child is the underlying table), or
5933
- a single-table semi-join nest
5935
We don't assign bits to such sj-nests because
5936
1. it is redundant (a "sequence" of one table cannot be interleaved
5938
2. we could run out of bits in the nested join bitset otherwise.
5940
if (nested_join->join_list.elements != 1)
5942
/* Don't assign bits to sj-nests */
5944
nested_join->nj_map.set(first_unused++);
5945
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
5950
return(first_unused);
5955
Return table number if there is only one table in sort order
5956
and group and order is compatible, else return 0.
5958
static Table *get_sort_by_table(Order *a, Order *b,TableList *tables)
5960
table_map map= (table_map) 0;
5963
a= b; // Only one need to be given
5967
for (; a && b; a=a->next,b=b->next)
5969
if (!(*a->item)->eq(*b->item,1))
5970
return (Table *) NULL;
5971
map|= a->item[0]->used_tables();
5973
if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
5974
return (Table *) NULL;
5976
for (; !(map & tables->table->map); tables= tables->next_leaf) {};
5977
if (map != tables->table->map)
5978
return (Table *) NULL; // More than one table
5979
return tables->table;
5983
Set nested_join_st::counter=0 in all nested joins in passed list.
5985
Recursively set nested_join_st::counter=0 for all nested joins contained in
5986
the passed join_list.
5988
@param join_list List of nested joins to process. It may also contain base
5989
tables which will be ignored.
5991
static void reset_nj_counters(List<TableList> *join_list)
5993
List_iterator<TableList> li(*join_list);
5995
while ((table= li++))
5997
nested_join_st *nested_join;
5998
if ((nested_join= table->getNestedJoin()))
6000
nested_join->counter_= 0;
6001
reset_nj_counters(&nested_join->join_list);
6008
Return 1 if second is a subpart of first argument.
6010
If first parts has different direction, change it to second part
6011
(group is sorted like order)
6013
static bool test_if_subpart(Order *a, Order *b)
6015
for (; a && b; a=a->next,b=b->next)
6017
if ((*a->item)->eq(*b->item,1))
6026
Nested joins perspective: Remove the last table from the join order.
6028
The algorithm is the reciprocal of check_interleaving_with_nj(), hence
6029
parent join nest nodes are updated only when the last table in its child
6030
node is removed. The ASCII graphic below will clarify.
6032
%A table nesting such as <tt> t1 x [ ( t2 x t3 ) x ( t4 x t5 ) ] </tt>is
6033
represented by the below join nest tree.
6041
t1 x [ (t2 x t3) x (t4 x t5) ]
6044
At the point in time when check_interleaving_with_nj() adds the table t5 to
6045
the query execution plan, QEP, it also directs the node named NJ2 to mark
6046
the table as covered. NJ2 does so by incrementing its @c counter
6047
member. Since all of NJ2's tables are now covered by the QEP, the algorithm
6048
proceeds up the tree to NJ1, incrementing its counter as well. All join
6049
nests are now completely covered by the QEP.
6051
restore_prev_nj_state() does the above in reverse. As seen above, the node
6052
NJ1 contains the nodes t2, t3, and NJ2. Its counter being equal to 3 means
6053
that the plan covers t2, t3, and NJ2, @e and that the sub-plan (t4 x t5)
6054
completely covers NJ2. The removal of t5 from the partial plan will first
6055
decrement NJ2's counter to 1. It will then detect that NJ2 went from being
6056
completely to partially covered, and hence the algorithm must continue
6057
upwards to NJ1 and decrement its counter to 2. %A subsequent removal of t4
6058
will however not influence NJ1 since it did not un-cover the last table in
6062
restore_prev_nj_state()
6063
last join table to remove, it is assumed to be the last in current
6068
Remove the last table from the partial join order and update the nested
6069
joins counters and join->cur_embedding_map. It is ok to call this
6070
function for the first table in join order (for which
6071
check_interleaving_with_nj has not been called)
6073
@param last join table to remove, it is assumed to be the last in current
6077
static void restore_prev_nj_state(JoinTable *last)
6079
TableList *last_emb= last->table->pos_in_table_list->getEmbedding();
6080
Join *join= last->join;
6081
for (;last_emb != NULL; last_emb= last_emb->getEmbedding())
6083
nested_join_st *nest= last_emb->getNestedJoin();
6085
bool was_fully_covered= nest->is_fully_covered();
6087
if (--nest->counter_ == 0)
6088
join->cur_embedding_map&= ~nest->nj_map;
6090
if (!was_fully_covered)
6093
join->cur_embedding_map|= nest->nj_map;
6098
Create a condition for a const reference and add this to the
6099
currenct select for the table.
6101
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)
6103
if (!join_tab->ref.key_parts)
6106
Item_cond_and *cond=new Item_cond_and();
6107
Table *table=join_tab->table;
6112
for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6114
Field *field=table->getField(table->key_info[join_tab->ref.key].key_part[i].fieldnr - 1);
6115
Item *value=join_tab->ref.items[i];
6116
cond->add(new Item_func_equal(new Item_field(field), value));
6118
if (session->is_fatal_error)
6122
cond->fix_fields(session, (Item**)&cond);
6123
if (join_tab->select)
6125
error=(int) cond->add(join_tab->select->cond);
6126
join_tab->select_cond=join_tab->select->cond=cond;
6128
else if ((join_tab->select= optimizer::make_select(join_tab->table, 0, 0, cond, 0,
6130
join_tab->select_cond=cond;
6132
return(error ? true : false);
6135
static void free_blobs(Field **ptr)
6137
for (; *ptr ; ptr++)
6139
if ((*ptr)->flags & BLOB_FLAG)
6140
((Field_blob *) (*ptr))->free();
6145
@} (end of group Query_Optimizer)
6148
} /* namespace drizzled */
added
removed
drizzled/join.cc
