1
/* - mode: c; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
4
* Copyright (C) 2008-2009 Sun Microsystems
6
* This program is free software; you can redistribute it and/or modify
7
* it under the terms of the GNU General Public License as published by
8
* the Free Software Foundation; either version 2 of the License, or
9
* (at your option) any later version.
11
* This program is distributed in the hope that it will be useful,
12
* but WITHOUT ANY WARRANTY; without even the implied warranty of
13
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
* GNU General Public License for more details.
16
* You should have received a copy of the GNU General Public License
17
* along with this program; if not, write to the Free Software
18
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24
* Implementation of the JOIN class
26
* @defgroup Query_Optimizer Query Optimizer
35
#include "drizzled/item/cache.h"
36
#include "drizzled/item/cmpfunc.h"
37
#include "drizzled/item/copy_string.h"
38
#include "drizzled/item/uint.h"
39
#include "drizzled/cached_item.h"
40
#include "drizzled/sql_base.h"
41
#include "drizzled/sql_select.h" /* include join.h */
42
#include "drizzled/lock.h"
43
#include "drizzled/nested_join.h"
44
#include "drizzled/join.h"
45
#include "drizzled/join_cache.h"
46
#include "drizzled/show.h"
47
#include "drizzled/field/blob.h"
48
#include "drizzled/optimizer/position.h"
49
#include "drizzled/optimizer/sargable_param.h"
50
#include "drizzled/optimizer/key_use.h"
51
#include "drizzled/optimizer/range.h"
52
#include "drizzled/optimizer/sum.h"
53
#include "drizzled/optimizer/explain_plan.h"
54
#include "drizzled/records.h"
55
#include "drizzled/probes.h"
56
#include "drizzled/internal/my_bit.h"
57
#include "drizzled/internal/my_sys.h"
58
#include "drizzled/internal/iocache.h"
67
extern plugin::StorageEngine *heap_engine;
68
extern std::bitset<12> test_flags;
70
/** Declarations of static functions used in this source file. */
71
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
72
static void calc_group_buffer(JOIN *join,order_st *group);
73
static bool alloc_group_fields(JOIN *join,order_st *group);
74
static uint32_t cache_record_length(JOIN *join, uint32_t index);
75
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
76
static bool get_best_combination(JOIN *join);
77
static void set_position(JOIN *join,
80
optimizer::KeyUse *key);
81
static bool choose_plan(JOIN *join,table_map join_tables);
82
static void best_access_path(JOIN *join, JoinTable *s,
84
table_map remaining_tables,
88
static void optimize_straight_join(JOIN *join, table_map join_tables);
89
static bool greedy_search(JOIN *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
90
static bool best_extension_by_limited_search(JOIN *join,
91
table_map remaining_tables,
96
uint32_t prune_level);
97
static uint32_t determine_search_depth(JOIN* join);
98
static bool make_simple_join(JOIN *join,Table *tmp_table);
99
static void make_outerjoin_info(JOIN *join);
100
static bool make_join_select(JOIN *join, optimizer::SqlSelect *select,COND *item);
101
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
102
static void update_depend_map(JOIN *join);
103
static void update_depend_map(JOIN *join, order_st *order);
104
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond, bool change_list, bool *simple_order);
105
static int return_zero_rows(JOIN *join,
110
uint64_t select_options,
113
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top);
114
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields, Item *having);
115
static int setup_without_group(Session *session,
116
Item **ref_pointer_array,
120
List<Item> &all_fields,
124
bool *hidden_group_fields);
125
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
126
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
127
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
128
static void reset_nj_counters(List<TableList> *join_list);
129
static bool test_if_subpart(order_st *a,order_st *b);
130
static void restore_prev_nj_state(JoinTable *last);
131
static uint32_t make_join_orderinfo(JOIN *join);
132
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
133
static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
136
Prepare of whole select (including sub queries in future).
139
Add check of calculation of GROUP functions and fields:
140
SELECT COUNT(*)+table.col1 from table1;
147
int JOIN::prepare(Item ***rref_pointer_array,
148
TableList *tables_init,
152
order_st *order_init,
153
order_st *group_init,
155
Select_Lex *select_lex_arg,
156
Select_Lex_Unit *unit_arg)
158
// to prevent double initialization on EXPLAIN
164
group_list= group_init;
166
tables_list= tables_init;
167
select_lex= select_lex_arg;
168
select_lex->join= this;
169
join_list= &select_lex->top_join_list;
170
union_part= unit_arg->is_union();
172
session->lex->current_select->is_item_list_lookup= 1;
174
If we have already executed SELECT, then it have not sense to prevent
175
its table from update (see unique_table())
177
if (session->derived_tables_processing)
178
select_lex->exclude_from_table_unique_test= true;
180
/* Check that all tables, fields, conds and order are ok */
182
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
183
setup_tables_and_check_access(session, &select_lex->context, join_list,
184
tables_list, &select_lex->leaf_tables,
188
TableList *table_ptr;
189
for (table_ptr= select_lex->leaf_tables;
191
table_ptr= table_ptr->next_leaf)
194
if (setup_wild(session, fields_list, &all_fields, wild_num) ||
195
select_lex->setup_ref_array(session, og_num) ||
196
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
198
setup_without_group(session, (*rref_pointer_array), tables_list,
199
select_lex->leaf_tables, fields_list,
200
all_fields, &conds, order, group_list,
201
&hidden_group_fields))
204
ref_pointer_array= *rref_pointer_array;
208
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
209
session->where="having clause";
210
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
211
select_lex->having_fix_field= 1;
212
bool having_fix_rc= (!having->fixed &&
213
(having->fix_fields(session, &having) ||
214
having->check_cols(1)));
215
select_lex->having_fix_field= 0;
216
if (having_fix_rc || session->is_error())
218
session->lex->allow_sum_func= save_allow_sum_func;
222
Item_subselect *subselect;
223
Item_in_subselect *in_subs= NULL;
225
Are we in a subquery predicate?
226
TODO: the block below will be executed for every PS execution without need.
228
if ((subselect= select_lex->master_unit()->item))
230
if (subselect->substype() == Item_subselect::IN_SUBS)
231
in_subs= (Item_in_subselect*)subselect;
234
bool do_materialize= true;
236
Check if the subquery predicate can be executed via materialization.
237
The required conditions are:
238
1. Subquery predicate is an IN/=ANY subq predicate
239
2. Subquery is a single SELECT (not a UNION)
240
3. Subquery is not a table-less query. In this case there is no
241
point in materializing.
242
4. Subquery predicate is a top-level predicate
243
(this implies it is not negated)
244
TODO: this is a limitation that should be lifeted once we
245
implement correct NULL semantics (WL#3830)
246
5. Subquery is non-correlated
248
This is an overly restrictive condition. It can be extended to:
249
(Subquery is non-correlated ||
250
Subquery is correlated to any query outer to IN predicate ||
251
(Subquery is correlated to the immediate outer query &&
252
Subquery !contains {GROUP BY, order_st BY [LIMIT],
253
aggregate functions) && subquery predicate is not under "NOT IN"))
254
6. No execution method was already chosen (by a prepared statement).
256
(*) The subquery must be part of a SELECT statement. The current
257
condition also excludes multi-table update statements.
259
We have to determine whether we will perform subquery materialization
260
before calling the IN=>EXISTS transformation, so that we know whether to
261
perform the whole transformation or only that part of it which wraps
262
Item_in_subselect in an Item_in_optimizer.
264
if (do_materialize &&
266
!select_lex->master_unit()->first_select()->next_select() && // 2
267
select_lex->master_unit()->first_select()->leaf_tables && // 3
268
session->lex->sql_command == SQLCOM_SELECT) // *
270
if (in_subs->is_top_level_item() && // 4
271
!in_subs->is_correlated && // 5
272
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
273
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
276
Item_subselect::trans_res trans_res;
277
if ((trans_res= subselect->select_transformer(this)) !=
278
Item_subselect::RES_OK)
280
return((trans_res == Item_subselect::RES_ERROR));
289
for (ord= order; ord; ord= ord->next)
291
Item *item= *ord->item;
292
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
293
item->split_sum_func(session, ref_pointer_array, all_fields);
297
if (having && having->with_sum_func)
298
having->split_sum_func(session, ref_pointer_array, all_fields,
300
if (select_lex->inner_sum_func_list)
302
Item_sum *end=select_lex->inner_sum_func_list;
303
Item_sum *item_sum= end;
306
item_sum= item_sum->next;
307
item_sum->split_sum_func(session, ref_pointer_array,
308
all_fields, item_sum->ref_by, false);
309
} while (item_sum != end);
312
if (select_lex->inner_refs_list.elements &&
313
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
317
Check if there are references to un-aggregated columns when computing
318
aggregate functions with implicit grouping (there is no GROUP BY).
320
MODE_ONLY_FULL_GROUP_BY is enabled here by default
323
select_lex->full_group_by_flag.test(NON_AGG_FIELD_USED) &&
324
select_lex->full_group_by_flag.test(SUM_FUNC_USED))
326
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
327
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
331
/* Caclulate the number of groups */
333
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
340
if (result && result->prepare(fields_list, unit_arg))
343
/* Init join struct */
344
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
345
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
346
this->group= group_list != 0;
349
#ifdef RESTRICTED_GROUP
350
if (sum_func_count && !group_list && (func_count || field_count))
352
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
356
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
358
if (alloc_func_list())
368
Remove the predicates pushed down into the subquery
371
JOIN::remove_subq_pushed_predicates()
372
where IN Must be NULL
373
OUT The remaining WHERE condition, or NULL
376
Given that this join will be executed using (unique|index)_subquery,
377
without "checking NULL", remove the predicates that were pushed down
380
If the subquery compares scalar values, we can remove the condition that
381
was wrapped into trig_cond (it will be checked when needed by the subquery
384
If the subquery compares row values, we need to keep the wrapped
385
equalities in the WHERE clause: when the left (outer) tuple has both NULL
386
and non-NULL values, we'll do a full table scan and will rely on the
387
equalities corresponding to non-NULL parts of left tuple to filter out
388
non-matching records.
390
TODO: We can remove the equalities that will be guaranteed to be true by the
391
fact that subquery engine will be using index lookup. This must be done only
392
for cases where there are no conversion errors of significance, e.g. 257
393
that is searched in a byte. But this requires homogenization of the return
394
codes of all Field*::store() methods.
396
void JOIN::remove_subq_pushed_predicates(Item **where)
398
if (conds->type() == Item::FUNC_ITEM &&
399
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
400
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
401
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
402
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
403
((Item_func *)conds)->arguments()[0]))
411
global select optimisation.
414
error code saved in field 'error'
423
// to prevent double initialization on EXPLAIN
428
session->set_proc_info("optimizing");
429
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
430
unit->select_limit_cnt);
431
/* select_limit is used to decide if we are likely to scan the whole table */
432
select_limit= unit->select_limit_cnt;
433
if (having || (select_options & OPTION_FOUND_ROWS))
434
select_limit= HA_POS_ERROR;
435
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
436
// Ignore errors of execution if option IGNORE present
437
if (session->lex->ignore)
438
session->lex->current_select->no_error= 1;
440
#ifdef HAVE_REF_TO_FIELDS // Not done yet
441
/* Add HAVING to WHERE if possible */
442
if (having && !group_list && !sum_func_count)
449
else if ((conds=new Item_cond_and(conds,having)))
452
Item_cond_and can't be fixed after creation, so we do not check
455
conds->fix_fields(session, &conds);
456
conds->change_ref_to_fields(session, tables_list);
457
conds->top_level_item();
463
/* Convert all outer joins to inner joins if possible */
464
conds= simplify_joins(this, join_list, conds, true);
465
build_bitmap_for_nested_joins(join_list, 0);
467
conds= optimize_cond(this, conds, join_list, &cond_value);
468
if (session->is_error())
475
having= optimize_cond(this, having, join_list, &having_value);
476
if (session->is_error())
481
if (select_lex->where)
482
select_lex->cond_value= cond_value;
483
if (select_lex->having)
484
select_lex->having_value= having_value;
486
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
487
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
488
{ /* Impossible cond */
489
zero_result_cause= having_value == Item::COND_FALSE ?
490
"Impossible HAVING" : "Impossible WHERE";
496
/* Optimize count(*), cmin() and cmax() */
497
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
501
optimizer::sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
502
to the WHERE conditions,
503
or 1 if all items were resolved,
504
or 0, or an error number HA_ERR_...
506
if ((res= optimizer::sum_query(select_lex->leaf_tables, all_fields, conds)))
508
if (res == HA_ERR_KEY_NOT_FOUND)
510
zero_result_cause= "No matching min/max row";
521
zero_result_cause= "No matching min/max row";
525
zero_result_cause= "Select tables optimized away";
526
tables_list= 0; // All tables resolved
528
Extract all table-independent conditions and replace the WHERE
529
clause with them. All other conditions were computed by optimizer::sum_query
530
and the MIN/MAX/COUNT function(s) have been replaced by constants,
531
so there is no need to compute the whole WHERE clause again.
532
Notice that make_cond_for_table() will always succeed to remove all
533
computed conditions, because optimizer::sum_query() is applicable only to
535
Preserve conditions for EXPLAIN.
537
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
539
COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
540
conds= table_independent_conds;
549
error= -1; // Error is sent to client
550
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
552
/* Calculate how to do the join */
553
session->set_proc_info("statistics");
554
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
555
session->is_fatal_error)
560
/* Remove distinct if only const tables */
561
select_distinct= select_distinct && (const_tables != tables);
562
session->set_proc_info("preparing");
563
if (result->initialize_tables(this))
565
return 1; // error == -1
567
if (const_table_map != found_const_table_map &&
568
!(select_options & SELECT_DESCRIBE) &&
570
!(conds->used_tables() & RAND_TABLE_BIT) ||
571
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
573
zero_result_cause= "no matching row in const table";
577
if (!(session->options & OPTION_BIG_SELECTS) &&
578
best_read > (double) session->variables.max_join_size &&
579
!(select_options & SELECT_DESCRIBE))
581
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
585
if (const_tables && !(select_options & SELECT_NO_UNLOCK))
586
mysql_unlock_some_tables(session, table, const_tables);
587
if (!conds && outer_join)
589
/* Handle the case where we have an OUTER JOIN without a WHERE */
590
conds=new Item_int((int64_t) 1,1); // Always true
592
select= optimizer::make_select(*table, const_table_map,
593
const_table_map, conds, 1, &error);
600
reset_nj_counters(join_list);
601
make_outerjoin_info(this);
604
Among the equal fields belonging to the same multiple equality
605
choose the one that is to be retrieved first and substitute
606
all references to these in where condition for a reference for
611
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
612
conds->update_used_tables();
616
Permorm the the optimization on fields evaluation mentioned above
617
for all on expressions.
619
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
621
if (*tab->on_expr_ref)
623
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
626
(*tab->on_expr_ref)->update_used_tables();
630
if (conds &&!outer_join && const_table_map != found_const_table_map &&
631
(select_options & SELECT_DESCRIBE) &&
632
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
634
conds=new Item_int((int64_t) 0,1); // Always false
637
if (make_join_select(this, select, conds))
640
"Impossible WHERE noticed after reading const tables";
641
return(0); // error == 0
644
error= -1; /* if goto err */
646
/* Optimize distinct away if possible */
648
order_st *org_order= order;
649
order= remove_constants(this, order,conds,1, &simple_order);
650
if (session->is_error())
657
If we are using order_st BY NULL or order_st BY const_expression,
658
return result in any order (even if we are using a GROUP BY)
660
if (!order && org_order)
664
Check if we can optimize away GROUP BY/DISTINCT.
665
We can do that if there are no aggregate functions, the
666
fields in DISTINCT clause (if present) and/or columns in GROUP BY
667
(if present) contain direct references to all key parts of
668
an unique index (in whatever order) and if the key parts of the
669
unique index cannot contain NULLs.
670
Note that the unique keys for DISTINCT and GROUP BY should not
671
be the same (as long as they are unique).
673
The FROM clause must contain a single non-constant table.
675
if (tables - const_tables == 1 && (group_list || select_distinct) &&
676
! tmp_table_param.sum_func_count &&
677
(! join_tab[const_tables].select ||
678
! join_tab[const_tables].select->quick ||
679
join_tab[const_tables].select->quick->get_type() !=
680
optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))
682
if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
685
We have found that grouping can be removed since groups correspond to
686
only one row anyway, but we still have to guarantee correct result
687
order. The line below effectively rewrites the query from GROUP BY
688
<fields> to order_st BY <fields>. There are two exceptions:
689
- if skip_sort_order is set (see above), then we can simply skip
691
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
692
with the GROUP BY ones, i.e. either one is a prefix of another.
693
We only check if the order_st BY is a prefix of GROUP BY. In this case
694
test_if_subpart() copies the ASC/DESC attributes from the original
696
If GROUP BY is a prefix of order_st BY, then it is safe to leave
699
if (! order || test_if_subpart(group_list, order))
700
order= skip_sort_order ? 0 : group_list;
702
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
703
rewritten to IGNORE INDEX FOR order_st BY(fields).
705
join_tab->table->keys_in_use_for_order_by=
706
join_tab->table->keys_in_use_for_group_by;
710
if (select_distinct &&
711
list_contains_unique_index(join_tab[const_tables].table,
712
find_field_in_item_list,
713
(void *) &fields_list))
718
if (group_list || tmp_table_param.sum_func_count)
720
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
723
else if (select_distinct && tables - const_tables == 1)
726
We are only using one table. In this case we change DISTINCT to a
728
- The GROUP BY can be done through indexes (no sort) and the order_st
729
BY only uses selected fields.
730
(In this case we can later optimize away GROUP BY and order_st BY)
731
- We are scanning the whole table without LIMIT
733
- We are using CALC_FOUND_ROWS
734
- We are using an order_st BY that can't be optimized away.
736
We don't want to use this optimization when we are using LIMIT
737
because in this case we can just create a temporary table that
738
holds LIMIT rows and stop when this table is full.
740
JoinTable *tab= &join_tab[const_tables];
741
bool all_order_fields_used;
743
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
744
&tab->table->keys_in_use_for_order_by);
745
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
746
order, fields_list, all_fields,
747
&all_order_fields_used)))
749
bool skip_group= (skip_sort_order &&
750
test_if_skip_sort_order(tab, group_list, select_limit, 1,
751
&tab->table->keys_in_use_for_group_by) != 0);
752
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
753
if ((skip_group && all_order_fields_used) ||
754
select_limit == HA_POS_ERROR ||
755
(order && !skip_sort_order))
757
/* Change DISTINCT to GROUP BY */
760
if (all_order_fields_used)
762
if (order && skip_sort_order)
765
Force MySQL to read the table in sorted order to get result in
768
tmp_table_param.quick_group=0;
772
group=1; // For end_write_group
777
else if (session->is_fatal_error) // End of memory
782
order_st *old_group_list;
783
group_list= remove_constants(this, (old_group_list= group_list), conds,
784
rollup.state == ROLLUP::STATE_NONE,
786
if (session->is_error())
791
if (old_group_list && !group_list)
794
if (!group_list && group)
796
order=0; // The output has only one row
798
select_distinct= 0; // No need in distinct for 1 row
799
group_optimized_away= 1;
802
calc_group_buffer(this, group_list);
803
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
805
if (test_if_subpart(group_list, order) ||
806
(!group_list && tmp_table_param.sum_func_count))
809
// Can't use sort on head table if using row cache
819
Check if we need to create a temporary table.
820
This has to be done if all tables are not already read (const tables)
821
and one of the following conditions holds:
822
- We are using DISTINCT (simple distinct's are already optimized away)
823
- We are using an order_st BY or GROUP BY on fields not in the first table
824
- We are using different order_st BY and GROUP BY orders
825
- The user wants us to buffer the result.
827
need_tmp= (const_tables != tables &&
828
((select_distinct || !simple_order || !simple_group) ||
829
(group_list && order) ||
830
test(select_options & OPTION_BUFFER_RESULT)));
832
uint32_t no_jbuf_after= make_join_orderinfo(this);
833
uint64_t select_opts_for_readinfo=
834
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
836
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
837
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
840
/* Create all structures needed for materialized subquery execution. */
841
if (setup_subquery_materialization())
844
/* Cache constant expressions in WHERE, HAVING, ON clauses. */
848
is this simple IN subquery?
850
if (!group_list && !order &&
851
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
852
tables == 1 && conds &&
858
if (join_tab[0].type == AM_EQ_REF && join_tab[0].ref.items[0]->name == in_left_expr_name)
860
remove_subq_pushed_predicates(&where);
861
save_index_subquery_explain_info(join_tab, where);
862
join_tab[0].type= AM_UNIQUE_SUBQUERY;
866
subselect_uniquesubquery_engine(session,
871
else if (join_tab[0].type == AM_REF &&
872
join_tab[0].ref.items[0]->name == in_left_expr_name)
874
remove_subq_pushed_predicates(&where);
875
save_index_subquery_explain_info(join_tab, where);
876
join_tab[0].type= AM_INDEX_SUBQUERY;
880
subselect_indexsubquery_engine(session,
888
else if (join_tab[0].type == AM_REF_OR_NULL &&
889
join_tab[0].ref.items[0]->name == in_left_expr_name &&
890
having->name == in_having_cond)
892
join_tab[0].type= AM_INDEX_SUBQUERY;
894
conds= remove_additional_cond(conds);
895
save_index_subquery_explain_info(join_tab, conds);
897
change_engine(new subselect_indexsubquery_engine(session,
907
Need to tell handlers that to play it safe, it should fetch all
908
columns of the primary key of the tables: this is because MySQL may
909
build row pointers for the rows, and for all columns of the primary key
910
the read set has not necessarily been set by the server code.
912
if (need_tmp || select_distinct || group_list || order)
914
for (uint32_t i = const_tables; i < tables; i++)
915
join_tab[i].table->prepare_for_position();
918
if (const_tables != tables)
921
Because filesort always does a full table scan or a quick range scan
922
we must add the removed reference to the select for the table.
923
We only need to do this when we have a simple_order or simple_group
924
as in other cases the join is done before the sort.
926
if ((order || group_list) &&
927
(join_tab[const_tables].type != AM_ALL) &&
928
(join_tab[const_tables].type != AM_REF_OR_NULL) &&
929
((order && simple_order) || (group_list && simple_group)))
931
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
936
if (!(select_options & SELECT_BIG_RESULT) &&
939
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
940
unit->select_limit_cnt, 0,
941
&join_tab[const_tables].table->
942
keys_in_use_for_group_by))) ||
944
tmp_table_param.quick_group)
946
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
951
Force using of tmp table if sorting by a SP or UDF function due to
952
their expensive and probably non-deterministic nature.
954
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
956
Item *item= *tmp_order->item;
957
if (item->is_expensive())
959
/* Force tmp table without sort */
960
need_tmp=1; simple_order=simple_group=0;
968
if (select_options & SELECT_DESCRIBE)
976
The loose index scan access method guarantees that all grouping or
977
duplicate row elimination (for distinct) is already performed
978
during data retrieval, and that all MIN/MAX functions are already
979
computed for each group. Thus all MIN/MAX functions should be
980
treated as regular functions, and there is no need to perform
981
grouping in the main execution loop.
982
Notice that currently loose index scan is applicable only for
983
single table queries, thus it is sufficient to test only the first
984
join_tab element of the plan for its access method.
986
if (join_tab->is_using_loose_index_scan())
987
tmp_table_param.precomputed_group_by= true;
989
/* Create a tmp table if distinct or if the sort is too complicated */
992
session->set_proc_info("Creating tmp table");
994
init_items_ref_array();
996
tmp_table_param.hidden_field_count= (all_fields.elements -
997
fields_list.elements);
998
order_st *tmp_group= ((!simple_group &&
999
! (test_flags.test(TEST_NO_KEY_GROUP))) ? group_list :
1002
Pushing LIMIT to the temporary table creation is not applicable
1003
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1004
there are aggregate functions, because in all these cases we need
1007
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1009
!session->lex->current_select->with_sum_func) ?
1010
select_limit : HA_POS_ERROR;
1012
if (!(exec_tmp_table1=
1013
create_tmp_table(session, &tmp_table_param, all_fields,
1015
group_list ? 0 : select_distinct,
1016
group_list && simple_group,
1025
We don't have to store rows in temp table that doesn't match HAVING if:
1026
- we are sorting the table and writing complete group rows to the
1028
- We are using DISTINCT without resolving the distinct as a GROUP BY
1031
If having is not handled here, it will be checked before the row
1032
is sent to the client.
1034
if (tmp_having && (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1037
/* if group or order on first table, sort first */
1038
if (group_list && simple_group)
1040
session->set_proc_info("Sorting for group");
1041
if (create_sort_index(session, this, group_list,
1042
HA_POS_ERROR, HA_POS_ERROR, false) ||
1043
alloc_group_fields(this, group_list) ||
1044
make_sum_func_list(all_fields, fields_list, 1) ||
1045
setup_sum_funcs(session, sum_funcs))
1053
if (make_sum_func_list(all_fields, fields_list, 0) ||
1054
setup_sum_funcs(session, sum_funcs))
1059
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1061
session->set_proc_info("Sorting for order");
1062
if (create_sort_index(session, this, order,
1063
HA_POS_ERROR, HA_POS_ERROR, true))
1072
Optimize distinct when used on some of the tables
1073
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1074
In this case we can stop scanning t2 when we have found one t1.a
1077
if (exec_tmp_table1->distinct)
1079
table_map used_tables= session->used_tables;
1080
JoinTable *last_join_tab= join_tab+tables-1;
1083
if (used_tables & last_join_tab->table->map)
1085
last_join_tab->not_used_in_distinct=1;
1086
} while (last_join_tab-- != join_tab);
1087
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1088
if (order && skip_sort_order)
1090
/* Should always succeed */
1091
if (test_if_skip_sort_order(&join_tab[const_tables],
1092
order, unit->select_limit_cnt, 0,
1093
&join_tab[const_tables].table->
1094
keys_in_use_for_order_by))
1100
If this join belongs to an uncacheable subquery save
1103
if (select_lex->uncacheable && !is_top_level_join() &&
1104
init_save_join_tab())
1113
Restore values in temporary join.
1115
void JOIN::restore_tmp()
1117
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1122
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1123
select_lex->offset_limit->val_uint() :
1128
if (exec_tmp_table1)
1130
exec_tmp_table1->cursor->extra(HA_EXTRA_RESET_STATE);
1131
exec_tmp_table1->cursor->ha_delete_all_rows();
1132
exec_tmp_table1->free_io_cache();
1133
exec_tmp_table1->filesort_free_buffers();
1135
if (exec_tmp_table2)
1137
exec_tmp_table2->cursor->extra(HA_EXTRA_RESET_STATE);
1138
exec_tmp_table2->cursor->ha_delete_all_rows();
1139
exec_tmp_table2->free_io_cache();
1140
exec_tmp_table2->filesort_free_buffers();
1143
set_items_ref_array(items0);
1146
memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);
1151
/* Reset of sum functions */
1154
Item_sum *func, **func_ptr= sum_funcs;
1155
while ((func= *(func_ptr++)))
1163
@brief Save the original join layout
1165
@details Saves the original join layout so it can be reused in
1166
re-execution and for EXPLAIN.
1168
@return Operation status
1170
@retval 1 error occurred.
1172
bool JOIN::init_save_join_tab()
1174
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
1176
error= 0; // Ensure that tmp_join.error= 0
1181
bool JOIN::save_join_tab()
1183
if (!join_tab_save && select_lex->master_unit()->uncacheable)
1185
if (!(join_tab_save= (JoinTable*)session->memdup((unsigned char*) join_tab,
1186
sizeof(JoinTable) * tables)))
1196
Note, that create_sort_index calls test_if_skip_sort_order and may
1197
finally replace sorting with index scan if there is a LIMIT clause in
1198
the query. It's never shown in EXPLAIN!
1201
When can we have here session->net.report_error not zero?
1205
List<Item> *columns_list= &fields_list;
1208
session->set_proc_info("executing");
1211
if (!tables_list && (tables || !select_lex->with_sum_func))
1213
/* Only test of functions */
1214
if (select_options & SELECT_DESCRIBE)
1216
optimizer::ExplainPlan planner(this,
1220
(zero_result_cause ? zero_result_cause : "No tables used"));
1221
planner.printPlan();
1225
result->send_fields(*columns_list);
1227
We have to test for 'conds' here as the WHERE may not be constant
1228
even if we don't have any tables for prepared statements or if
1229
conds uses something like 'rand()'.
1231
if (cond_value != Item::COND_FALSE &&
1232
(!conds || conds->val_int()) &&
1233
(!having || having->val_int()))
1235
if (do_send_rows && result->send_data(fields_list))
1239
error= (int) result->send_eof();
1240
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
1245
error= (int) result->send_eof();
1249
/* Single select (without union) always returns 0 or 1 row */
1250
session->limit_found_rows= send_records;
1251
session->examined_row_count= 0;
1255
Don't reset the found rows count if there're no tables as
1256
FOUND_ROWS() may be called. Never reset the examined row count here.
1257
It must be accumulated from all join iterations of all join parts.
1260
session->limit_found_rows= 0;
1262
if (zero_result_cause)
1264
(void) return_zero_rows(this, result, select_lex->leaf_tables,
1266
send_row_on_empty_set(),
1273
if (select_options & SELECT_DESCRIBE)
1276
Check if we managed to optimize order_st BY away and don't use temporary
1277
table to resolve order_st BY: in that case, we only may need to do
1278
filesort for GROUP BY.
1280
if (!order && !no_order && (!skip_sort_order || !need_tmp))
1282
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
1284
simple_order= simple_group;
1287
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
1289
if (const_tables == tables
1290
|| ((simple_order || skip_sort_order)
1291
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
1295
optimizer::ExplainPlan planner(this,
1297
order != 0 && ! skip_sort_order,
1299
! tables ? "No tables used" : NULL);
1300
planner.printPlan();
1304
JOIN *curr_join= this;
1305
List<Item> *curr_all_fields= &all_fields;
1306
List<Item> *curr_fields_list= &fields_list;
1307
Table *curr_tmp_table= 0;
1309
Initialize examined rows here because the values from all join parts
1310
must be accumulated in examined_row_count. Hence every join
1311
iteration must count from zero.
1313
curr_join->examined_rows= 0;
1315
/* Create a tmp table if distinct or if the sort is too complicated */
1321
We are in a non cacheable sub query. Get the saved join structure
1323
(curr_join may have been modified during last exection and we need
1326
curr_join= tmp_join;
1328
curr_tmp_table= exec_tmp_table1;
1330
/* Copy data to the temporary table */
1331
session->set_proc_info("Copying to tmp table");
1332
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
1333
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1334
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1339
curr_tmp_table->cursor->info(HA_STATUS_VARIABLE);
1341
if (curr_join->having)
1342
curr_join->having= curr_join->tmp_having= 0; // Allready done
1344
/* Change sum_fields reference to calculated fields in tmp_table */
1345
curr_join->all_fields= *curr_all_fields;
1348
items1= items0 + all_fields.elements;
1349
if (sort_and_group || curr_tmp_table->group)
1351
if (change_to_use_tmp_fields(session, items1,
1352
tmp_fields_list1, tmp_all_fields1,
1353
fields_list.elements, all_fields))
1358
if (change_refs_to_tmp_fields(session, items1,
1359
tmp_fields_list1, tmp_all_fields1,
1360
fields_list.elements, all_fields))
1363
curr_join->tmp_all_fields1= tmp_all_fields1;
1364
curr_join->tmp_fields_list1= tmp_fields_list1;
1365
curr_join->items1= items1;
1367
curr_all_fields= &tmp_all_fields1;
1368
curr_fields_list= &tmp_fields_list1;
1369
curr_join->set_items_ref_array(items1);
1371
if (sort_and_group || curr_tmp_table->group)
1373
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
1374
+ curr_join->tmp_table_param.func_count;
1375
curr_join->tmp_table_param.sum_func_count= 0;
1376
curr_join->tmp_table_param.func_count= 0;
1380
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
1381
curr_join->tmp_table_param.func_count= 0;
1384
if (curr_tmp_table->group)
1385
{ // Already grouped
1386
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
1387
curr_join->order= curr_join->group_list; /* order by group */
1388
curr_join->group_list= 0;
1392
If we have different sort & group then we must sort the data by group
1393
and copy it to another tmp table
1394
This code is also used if we are using distinct something
1395
we haven't been able to store in the temporary table yet
1396
like SEC_TO_TIME(SUM(...)).
1399
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
1400
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
1401
{ /* Must copy to another table */
1402
/* Free first data from old join */
1403
curr_join->join_free();
1404
if (make_simple_join(curr_join, curr_tmp_table))
1406
calc_group_buffer(curr_join, group_list);
1407
count_field_types(select_lex, &curr_join->tmp_table_param,
1408
curr_join->tmp_all_fields1,
1409
curr_join->select_distinct && !curr_join->group_list);
1410
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
1411
- curr_join->tmp_fields_list1.elements;
1413
if (exec_tmp_table2)
1414
curr_tmp_table= exec_tmp_table2;
1417
/* group data to new table */
1420
If the access method is loose index scan then all MIN/MAX
1421
functions are precomputed, and should be treated as regular
1422
functions. See extended comment in JOIN::exec.
1424
if (curr_join->join_tab->is_using_loose_index_scan())
1425
curr_join->tmp_table_param.precomputed_group_by= true;
1427
if (!(curr_tmp_table=
1428
exec_tmp_table2= create_tmp_table(session,
1429
&curr_join->tmp_table_param,
1432
curr_join->select_distinct &&
1433
!curr_join->group_list,
1434
1, curr_join->select_options,
1438
curr_join->exec_tmp_table2= exec_tmp_table2;
1440
if (curr_join->group_list)
1442
session->set_proc_info("Creating sort index");
1443
if (curr_join->join_tab == join_tab && save_join_tab())
1447
if (create_sort_index(session, curr_join, curr_join->group_list,
1448
HA_POS_ERROR, HA_POS_ERROR, false) ||
1449
make_group_fields(this, curr_join))
1453
sortorder= curr_join->sortorder;
1456
session->set_proc_info("Copying to group table");
1458
if (curr_join != this)
1462
curr_join->sum_funcs= sum_funcs2;
1463
curr_join->sum_funcs_end= sum_funcs_end2;
1467
curr_join->alloc_func_list();
1468
sum_funcs2= curr_join->sum_funcs;
1469
sum_funcs_end2= curr_join->sum_funcs_end;
1472
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
1474
curr_join->group_list= 0;
1476
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
1477
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1479
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
1480
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1485
end_read_record(&curr_join->join_tab->read_record);
1486
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1487
curr_join->join_tab[0].table= 0; // Table is freed
1489
// No sum funcs anymore
1492
items2= items1 + all_fields.elements;
1493
if (change_to_use_tmp_fields(session, items2,
1494
tmp_fields_list2, tmp_all_fields2,
1495
fields_list.elements, tmp_all_fields1))
1497
curr_join->tmp_fields_list2= tmp_fields_list2;
1498
curr_join->tmp_all_fields2= tmp_all_fields2;
1500
curr_fields_list= &curr_join->tmp_fields_list2;
1501
curr_all_fields= &curr_join->tmp_all_fields2;
1502
curr_join->set_items_ref_array(items2);
1503
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
1504
curr_join->tmp_table_param.sum_func_count= 0;
1506
if (curr_tmp_table->distinct)
1507
curr_join->select_distinct=0; /* Each row is unique */
1509
curr_join->join_free(); /* Free quick selects */
1510
if (curr_join->select_distinct && ! curr_join->group_list)
1512
session->set_proc_info("Removing duplicates");
1513
if (curr_join->tmp_having)
1514
curr_join->tmp_having->update_used_tables();
1516
if (remove_duplicates(curr_join, curr_tmp_table,
1517
*curr_fields_list, curr_join->tmp_having))
1520
curr_join->tmp_having=0;
1521
curr_join->select_distinct=0;
1523
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
1524
if (make_simple_join(curr_join, curr_tmp_table))
1526
calc_group_buffer(curr_join, curr_join->group_list);
1527
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
1531
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
1533
if (make_group_fields(this, curr_join))
1539
init_items_ref_array();
1540
items3= ref_pointer_array + (all_fields.elements*4);
1541
setup_copy_fields(session, &curr_join->tmp_table_param,
1542
items3, tmp_fields_list3, tmp_all_fields3,
1543
curr_fields_list->elements, *curr_all_fields);
1544
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
1545
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
1546
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
1547
curr_join->tmp_all_fields3= tmp_all_fields3;
1548
curr_join->tmp_fields_list3= tmp_fields_list3;
1552
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
1553
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
1554
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
1556
curr_fields_list= &tmp_fields_list3;
1557
curr_all_fields= &tmp_all_fields3;
1558
curr_join->set_items_ref_array(items3);
1560
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1562
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
1563
session->is_fatal_error)
1566
if (curr_join->group_list || curr_join->order)
1568
session->set_proc_info("Sorting result");
1569
/* If we have already done the group, add HAVING to sorted table */
1570
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
1572
// Some tables may have been const
1573
curr_join->tmp_having->update_used_tables();
1574
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];
1575
table_map used_tables= (curr_join->const_table_map |
1576
curr_table->table->map);
1578
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
1579
if (sort_table_cond)
1581
if (!curr_table->select)
1582
if (!(curr_table->select= new optimizer::SqlSelect))
1584
if (!curr_table->select->cond)
1585
curr_table->select->cond= sort_table_cond;
1586
else // This should never happen
1588
if (!(curr_table->select->cond=
1589
new Item_cond_and(curr_table->select->cond,
1593
Item_cond_and do not need fix_fields for execution, its parameters
1594
are fixed or do not need fix_fields, too
1596
curr_table->select->cond->quick_fix_field();
1598
curr_table->select_cond= curr_table->select->cond;
1599
curr_table->select_cond->top_level_item();
1600
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
1607
curr_join->select_limit= HA_POS_ERROR;
1611
We can abort sorting after session->select_limit rows if we there is no
1612
WHERE clause for any tables after the sorted one.
1614
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
1615
JoinTable *end_table= &curr_join->join_tab[curr_join->tables];
1616
for (; curr_table < end_table ; curr_table++)
1619
table->keyuse is set in the case there was an original WHERE clause
1620
on the table that was optimized away.
1622
if (curr_table->select_cond ||
1623
(curr_table->keyuse && !curr_table->first_inner))
1625
/* We have to sort all rows */
1626
curr_join->select_limit= HA_POS_ERROR;
1631
if (curr_join->join_tab == join_tab && save_join_tab())
1634
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
1635
chose FILESORT to be faster than INDEX SCAN or there is no
1636
suitable index present.
1637
Note, that create_sort_index calls test_if_skip_sort_order and may
1638
finally replace sorting with index scan if there is a LIMIT clause in
1639
the query. XXX: it's never shown in EXPLAIN!
1640
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
1642
if (create_sort_index(session, curr_join,
1643
curr_join->group_list ?
1644
curr_join->group_list : curr_join->order,
1645
curr_join->select_limit,
1646
(select_options & OPTION_FOUND_ROWS ?
1647
HA_POS_ERROR : unit->select_limit_cnt),
1648
curr_join->group_list ? true : false))
1651
sortorder= curr_join->sortorder;
1652
if (curr_join->const_tables != curr_join->tables &&
1653
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
1656
If no IO cache exists for the first table then we are using an
1657
INDEX SCAN and no filesort. Thus we should not remove the sorted
1658
attribute on the INDEX SCAN.
1664
/* XXX: When can we have here session->is_error() not zero? */
1665
if (session->is_error())
1667
error= session->is_error();
1670
curr_join->having= curr_join->tmp_having;
1671
curr_join->fields= curr_fields_list;
1673
session->set_proc_info("Sending data");
1674
result->send_fields(*curr_fields_list);
1675
error= do_select(curr_join, curr_fields_list, NULL);
1676
session->limit_found_rows= curr_join->send_records;
1678
/* Accumulate the counts from all join iterations of all join parts. */
1679
session->examined_row_count+= curr_join->examined_rows;
1682
With EXPLAIN EXTENDED we have to restore original ref_array
1683
for a derived table which is always materialized.
1684
Otherwise we would not be able to print the query correctly.
1686
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
1687
set_items_ref_array(items0);
1696
Return error that hold JOIN.
1700
select_lex->join= 0;
1704
if (join_tab != tmp_join->join_tab)
1706
JoinTable *tab, *end;
1707
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
1710
tmp_join->tmp_join= 0;
1711
tmp_table_param.copy_field=0;
1712
return(tmp_join->destroy());
1717
if (exec_tmp_table1)
1718
exec_tmp_table1->free_tmp_table(session);
1719
if (exec_tmp_table2)
1720
exec_tmp_table2->free_tmp_table(session);
1722
delete_dynamic(&keyuse);
1727
Setup for execution all subqueries of a query, for which the optimizer
1728
chose hash semi-join.
1730
@details Iterate over all subqueries of the query, and if they are under an
1731
IN predicate, and the optimizer chose to compute it via hash semi-join:
1732
- try to initialize all data structures needed for the materialized execution
1733
of the IN predicate,
1734
- if this fails, then perform the IN=>EXISTS transformation which was
1735
previously blocked during JOIN::prepare.
1737
This method is part of the "code generation" query processing phase.
1739
This phase must be called after substitute_for_best_equal_field() because
1740
that function may replace items with other items from a multiple equality,
1741
and we need to reference the correct items in the index access method of the
1744
@return Operation status
1745
@retval false success.
1746
@retval true error occurred.
1748
bool JOIN::setup_subquery_materialization()
1750
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1751
un= un->next_unit())
1753
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
1755
Item_subselect *subquery_predicate= sl->master_unit()->item;
1756
if (subquery_predicate &&
1757
subquery_predicate->substype() == Item_subselect::IN_SUBS)
1759
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
1760
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
1761
in_subs->setup_engine())
1770
Partially cleanup JOIN after it has executed: close index or rnd read
1771
(table cursors), free quick selects.
1773
This function is called in the end of execution of a JOIN, before the used
1774
tables are unlocked and closed.
1776
For a join that is resolved using a temporary table, the first sweep is
1777
performed against actual tables and an intermediate result is inserted
1778
into the temprorary table.
1779
The last sweep is performed against the temporary table. Therefore,
1780
the base tables and associated buffers used to fill the temporary table
1781
are no longer needed, and this function is called to free them.
1783
For a join that is performed without a temporary table, this function
1784
is called after all rows are sent, but before EOF packet is sent.
1786
For a simple SELECT with no subqueries this function performs a full
1787
cleanup of the JOIN and calls mysql_unlock_read_tables to free used base
1790
If a JOIN is executed for a subquery or if it has a subquery, we can't
1791
do the full cleanup and need to do a partial cleanup only.
1792
- If a JOIN is not the top level join, we must not unlock the tables
1793
because the outer select may not have been evaluated yet, and we
1794
can't unlock only selected tables of a query.
1795
- Additionally, if this JOIN corresponds to a correlated subquery, we
1796
should not free quick selects and join buffers because they will be
1797
needed for the next execution of the correlated subquery.
1798
- However, if this is a JOIN for a [sub]select, which is not
1799
a correlated subquery itself, but has subqueries, we can free it
1800
fully and also free JOINs of all its subqueries. The exception
1801
is a subquery in SELECT list, e.g: @n
1802
SELECT a, (select cmax(b) from t1) group by c @n
1803
This subquery will not be evaluated at first sweep and its value will
1804
not be inserted into the temporary table. Instead, it's evaluated
1805
when selecting from the temporary table. Therefore, it can't be freed
1806
here even though it's not correlated.
1809
Unlock tables even if the join isn't top level select in the tree
1811
void JOIN::join_free()
1813
Select_Lex_Unit *tmp_unit;
1816
Optimization: if not EXPLAIN and we are done with the JOIN,
1819
bool full= (!select_lex->uncacheable && !session->lex->describe);
1820
bool can_unlock= full;
1824
for (tmp_unit= select_lex->first_inner_unit();
1826
tmp_unit= tmp_unit->next_unit())
1827
for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
1829
Item_subselect *subselect= sl->master_unit()->item;
1830
bool full_local= full && (!subselect || subselect->is_evaluated());
1832
If this join is evaluated, we can fully clean it up and clean up all
1833
its underlying joins even if they are correlated -- they will not be
1834
used any more anyway.
1835
If this join is not yet evaluated, we still must clean it up to
1836
close its table cursors -- it may never get evaluated, as in case of
1837
... HAVING false OR a IN (SELECT ...))
1838
but all table cursors must be closed before the unlock.
1840
sl->cleanup_all_joins(full_local);
1841
/* Can't unlock if at least one JOIN is still needed */
1842
can_unlock= can_unlock && full_local;
1846
We are not using tables anymore
1847
Unlock all tables. We may be in an INSERT .... SELECT statement.
1849
if (can_unlock && lock && session->lock &&
1850
!(select_options & SELECT_NO_UNLOCK) &&
1851
!select_lex->subquery_in_having &&
1852
(select_lex == (session->lex->unit.fake_select_lex ?
1853
session->lex->unit.fake_select_lex : &session->lex->select_lex)))
1856
TODO: unlock tables even if the join isn't top level select in the
1859
mysql_unlock_read_tables(session, lock); // Don't free join->lock
1868
Free resources of given join.
1870
@param fill true if we should free all resources, call with full==1
1871
should be last, before it this function can be called with
1875
With subquery this function definitely will be called several times,
1876
but even for simple query it can be called several times.
1878
void JOIN::cleanup(bool full)
1882
JoinTable *tab,*end;
1884
Only a sorted table may be cached. This sorted table is always the
1885
first non const table in join->table
1887
if (tables > const_tables) // Test for not-const tables
1889
table[const_tables]->free_io_cache();
1890
table[const_tables]->filesort_free_buffers(full);
1895
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1901
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1904
tab->table->cursor->ha_index_or_rnd_end();
1909
We are not using tables anymore
1910
Unlock all tables. We may be in an INSERT .... SELECT statement.
1915
tmp_table_param.copy_field= 0;
1916
group_fields.delete_elements();
1918
We can't call delete_elements() on copy_funcs as this will cause
1919
problems in free_elements() as some of the elements are then deleted.
1921
tmp_table_param.copy_funcs.empty();
1923
If we have tmp_join and 'this' JOIN is not tmp_join and
1924
tmp_table_param.copy_field's of them are equal then we have to remove
1925
pointer to tmp_table_param.copy_field from tmp_join, because it qill
1926
be removed in tmp_table_param.cleanup().
1930
tmp_join->tmp_table_param.copy_field ==
1931
tmp_table_param.copy_field)
1933
tmp_join->tmp_table_param.copy_field=
1934
tmp_join->tmp_table_param.save_copy_field= 0;
1936
tmp_table_param.cleanup();
1942
used only in JOIN::clear
1944
static void clear_tables(JOIN *join)
1947
must clear only the non-const tables, as const tables
1948
are not re-calculated.
1950
for (uint32_t i= join->const_tables; i < join->tables; i++)
1951
join->table[i]->mark_as_null_row(); // All fields are NULL
1955
Make an array of pointers to sum_functions to speed up
1956
sum_func calculation.
1963
bool JOIN::alloc_func_list()
1965
uint32_t func_count, group_parts;
1967
func_count= tmp_table_param.sum_func_count;
1969
If we are using rollup, we need a copy of the summary functions for
1972
if (rollup.state != ROLLUP::STATE_NONE)
1973
func_count*= (send_group_parts+1);
1975
group_parts= send_group_parts;
1977
If distinct, reserve memory for possible
1978
disctinct->group_by optimization
1980
if (select_distinct)
1982
group_parts+= fields_list.elements;
1984
If the order_st clause is specified then it's possible that
1985
it also will be optimized, so reserve space for it too
1990
for (ord= order; ord; ord= ord->next)
1995
/* This must use calloc() as rollup_make_fields depends on this */
1996
sum_funcs= (Item_sum**) session->calloc(sizeof(Item_sum**) * (func_count+1) +
1997
sizeof(Item_sum***) * (group_parts+1));
1998
sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
1999
return(sum_funcs == 0);
2003
Initialize 'sum_funcs' array with all Item_sum objects.
2005
@param field_list All items
2006
@param send_fields Items in select list
2007
@param before_group_by Set to 1 if this is called before GROUP BY handling
2008
@param recompute Set to true if sum_funcs must be recomputed
2015
bool JOIN::make_sum_func_list(List<Item> &field_list,
2016
List<Item> &send_fields,
2017
bool before_group_by,
2020
List_iterator_fast<Item> it(field_list);
2024
if (*sum_funcs && !recompute)
2025
return(false); /* We have already initialized sum_funcs. */
2030
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2031
(!((Item_sum*) item)->depended_from() ||
2032
((Item_sum *)item)->depended_from() == select_lex))
2033
*func++= (Item_sum*) item;
2035
if (before_group_by && rollup.state == ROLLUP::STATE_INITED)
2037
rollup.state= ROLLUP::STATE_READY;
2038
if (rollup_make_fields(field_list, send_fields, &func))
2039
return(true); // Should never happen
2041
else if (rollup.state == ROLLUP::STATE_NONE)
2043
for (uint32_t i=0 ; i <= send_group_parts ;i++)
2044
sum_funcs_end[i]= func;
2046
else if (rollup.state == ROLLUP::STATE_READY)
2047
return(false); // Don't put end marker
2048
*func=0; // End marker
2052
/** Allocate memory needed for other rollup functions. */
2053
bool JOIN::rollup_init()
2058
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2059
rollup.state= ROLLUP::STATE_INITED;
2062
Create pointers to the different sum function groups
2063
These are updated by rollup_make_fields()
2065
tmp_table_param.group_parts= send_group_parts;
2067
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
2069
sizeof(List<Item>) +
2070
ref_pointer_array_size)
2071
* send_group_parts )))
2074
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
2075
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
2076
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
2079
Prepare space for field list for the different levels
2080
These will be filled up in rollup_make_fields()
2082
for (i= 0 ; i < send_group_parts ; i++)
2084
rollup.null_items[i]= new (session->mem_root) Item_null_result();
2085
List<Item> *rollup_fields= &rollup.fields[i];
2086
rollup_fields->empty();
2087
rollup.ref_pointer_arrays[i]= ref_array;
2088
ref_array+= all_fields.elements;
2090
for (i= 0 ; i < send_group_parts; i++)
2092
for (j=0 ; j < fields_list.elements ; j++)
2093
rollup.fields[i].push_back(rollup.null_items[i]);
2095
List_iterator<Item> it(all_fields);
2097
while ((item= it++))
2099
order_st *group_tmp;
2100
bool found_in_group= 0;
2102
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2104
if (*group_tmp->item == item)
2106
item->maybe_null= 1;
2108
if (item->const_item())
2111
For ROLLUP queries each constant item referenced in GROUP BY list
2112
is wrapped up into an Item_func object yielding the same value
2113
as the constant item. The objects of the wrapper class are never
2114
considered as constant items and besides they inherit all
2115
properties of the Item_result_field class.
2116
This wrapping allows us to ensure writing constant items
2117
into temporary tables whenever the result of the ROLLUP
2118
operation has to be written into a temporary table, e.g. when
2119
ROLLUP is used together with DISTINCT in the SELECT list.
2120
Usually when creating temporary tables for a intermidiate
2121
result we do not include fields for constant expressions.
2123
Item* new_item= new Item_func_rollup_const(item);
2126
new_item->fix_fields(session, (Item **) 0);
2127
session->change_item_tree(it.ref(), new_item);
2128
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
2130
if (*tmp->item == item)
2131
session->change_item_tree(tmp->item, new_item);
2136
if (item->type() == Item::FUNC_ITEM && !found_in_group)
2138
bool changed= false;
2139
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
2142
We have to prevent creation of a field in a temporary table for
2143
an expression that contains GROUP BY attributes.
2144
Marking the expression item as 'with_sum_func' will ensure this.
2147
item->with_sum_func= 1;
2154
Fill up rollup structures with pointers to fields to use.
2156
Creates copies of item_sum items for each sum level.
2158
@param fields_arg List of all fields (hidden and real ones)
2159
@param sel_fields Pointer to selected fields
2160
@param func Store here a pointer to all fields
2164
In this case func is pointing to next not used element.
2168
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2170
List_iterator_fast<Item> it(fields_arg);
2171
Item *first_field= sel_fields.head();
2175
Create field lists for the different levels
2177
The idea here is to have a separate field list for each rollup level to
2178
avoid all runtime checks of which columns should be NULL.
2180
The list is stored in reverse order to get sum function in such an order
2181
in func that it makes it easy to reset them with init_sum_functions()
2183
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2185
rollup.fields[0] will contain list where a,b,c is NULL
2186
rollup.fields[1] will contain list where b,c is NULL
2188
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
2190
sum_funcs_end[0] points to all sum functions
2191
sum_funcs_end[1] points to all sum functions, except grand totals
2195
for (level=0 ; level < send_group_parts ; level++)
2198
uint32_t pos= send_group_parts - level -1;
2199
bool real_fields= 0;
2201
List_iterator<Item> new_it(rollup.fields[pos]);
2202
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
2203
order_st *start_group;
2205
/* Point to first hidden field */
2206
Item **ref_array= ref_array_start + fields_arg.elements-1;
2208
/* Remember where the sum functions ends for the previous level */
2209
sum_funcs_end[pos+1]= *func;
2211
/* Find the start of the group for this level */
2212
for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
2216
while ((item= it++))
2218
if (item == first_field)
2220
real_fields= 1; // End of hidden fields
2221
ref_array= ref_array_start;
2224
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2225
(!((Item_sum*) item)->depended_from() ||
2226
((Item_sum *)item)->depended_from() == select_lex))
2230
This is a top level summary function that must be replaced with
2231
a sum function that is reset for this level.
2233
NOTE: This code creates an object which is not that nice in a
2234
sub select. Fortunately it's not common to have rollup in
2237
item= item->copy_or_same(session);
2238
((Item_sum*) item)->make_unique();
2239
*(*func)= (Item_sum*) item;
2244
/* Check if this is something that is part of this group by */
2245
order_st *group_tmp;
2246
for (group_tmp= start_group, i= pos ;
2247
group_tmp ; group_tmp= group_tmp->next, i++)
2249
if (*group_tmp->item == item)
2252
This is an element that is used by the GROUP BY and should be
2253
set to NULL in this level
2255
Item_null_result *null_item= new (session->mem_root) Item_null_result();
2258
item->maybe_null= 1; // Value will be null sometimes
2259
null_item->result_field= item->get_tmp_table_field();
2268
(void) new_it++; // Point to next item
2269
new_it.replace(item); // Replace previous
2276
sum_funcs_end[0]= *func; // Point to last function
2281
Send all rollup levels higher than the current one to the client.
2285
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2288
@param idx Level we are on:
2289
- 0 = Total sum level
2290
- 1 = First group changed (a)
2291
- 2 = Second group changed (a,b)
2296
1 If send_data_failed()
2298
int JOIN::rollup_send_data(uint32_t idx)
2301
for (i= send_group_parts ; i-- > idx ; )
2303
/* Get reference pointers to sum functions in place */
2304
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2305
ref_pointer_array_size);
2306
if ((!having || having->val_int()))
2308
if (send_records < unit->select_limit_cnt && do_send_rows &&
2309
result->send_data(rollup.fields[i]))
2314
/* Restore ref_pointer_array */
2315
set_items_ref_array(current_ref_pointer_array);
2320
Write all rollup levels higher than the current one to a temp table.
2324
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
2327
@param idx Level we are on:
2328
- 0 = Total sum level
2329
- 1 = First group changed (a)
2330
- 2 = Second group changed (a,b)
2331
@param table reference to temp table
2336
1 if write_data_failed()
2338
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
2341
for (i= send_group_parts ; i-- > idx ; )
2343
/* Get reference pointers to sum functions in place */
2344
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2345
ref_pointer_array_size);
2346
if ((!having || having->val_int()))
2350
List_iterator_fast<Item> it(rollup.fields[i]);
2351
while ((item= it++))
2353
if (item->type() == Item::NULL_ITEM && item->is_result_field())
2354
item->save_in_result_field(1);
2356
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2357
if ((write_error= table_arg->cursor->ha_write_row(table_arg->record[0])))
2359
if (create_myisam_from_heap(session, table_arg,
2360
tmp_table_param.start_recinfo,
2361
&tmp_table_param.recinfo,
2367
/* Restore ref_pointer_array */
2368
set_items_ref_array(current_ref_pointer_array);
2373
clear results if there are not rows found for group
2374
(end_send_group/end_write_group)
2379
copy_fields(&tmp_table_param);
2383
Item_sum *func, **func_ptr= sum_funcs;
2384
while ((func= *(func_ptr++)))
2390
change select_result object of JOIN.
2392
@param res new select_result object
2399
bool JOIN::change_result(select_result *res)
2402
if (result->prepare(fields_list, select_lex->master_unit()))
2410
Cache constant expressions in WHERE, HAVING, ON conditions.
2413
void JOIN::cache_const_exprs()
2415
bool cache_flag= false;
2416
bool *analyzer_arg= &cache_flag;
2418
/* No need in cache if all tables are constant. */
2419
if (const_tables == tables)
2423
conds->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2424
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2427
having->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2428
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2430
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
2432
if (*tab->on_expr_ref)
2435
(*tab->on_expr_ref)->compile(&Item::cache_const_expr_analyzer,
2436
(unsigned char **)&analyzer_arg,
2437
&Item::cache_const_expr_transformer,
2438
(unsigned char *)&cache_flag);
2446
Process one record of the nested loop join.
2450
This function will evaluate parts of WHERE/ON clauses that are
2451
applicable to the partial record on hand and in case of success
2452
submit this record to the next level of the nested loop.
2454
enum_nested_loop_state evaluate_join_record(JOIN *join, JoinTable *join_tab, int error)
2456
bool not_used_in_distinct= join_tab->not_used_in_distinct;
2457
ha_rows found_records= join->found_records;
2458
COND *select_cond= join_tab->select_cond;
2460
if (error > 0 || (join->session->is_error())) // Fatal error
2461
return NESTED_LOOP_ERROR;
2463
return NESTED_LOOP_NO_MORE_ROWS;
2464
if (join->session->killed) // Aborted by user
2466
join->session->send_kill_message();
2467
return NESTED_LOOP_KILLED;
2469
if (!select_cond || select_cond->val_int())
2472
There is no select condition or the attached pushed down
2473
condition is true => a match is found.
2476
while (join_tab->first_unmatched && found)
2479
The while condition is always false if join_tab is not
2480
the last inner join table of an outer join operation.
2482
JoinTable *first_unmatched= join_tab->first_unmatched;
2484
Mark that a match for current outer table is found.
2485
This activates push down conditional predicates attached
2486
to the all inner tables of the outer join.
2488
first_unmatched->found= 1;
2489
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2491
if (tab->table->reginfo.not_exists_optimize)
2492
return NESTED_LOOP_NO_MORE_ROWS;
2493
/* Check all predicates that has just been activated. */
2495
Actually all predicates non-guarded by first_unmatched->found
2496
will be re-evaluated again. It could be fixed, but, probably,
2497
it's not worth doing now.
2499
if (tab->select_cond && !tab->select_cond->val_int())
2501
/* The condition attached to table tab is false */
2502
if (tab == join_tab)
2507
Set a return point if rejected predicate is attached
2508
not to the last table of the current nest level.
2510
join->return_tab= tab;
2511
return NESTED_LOOP_OK;
2516
Check whether join_tab is not the last inner table
2517
for another embedding outer join.
2519
if ((first_unmatched= first_unmatched->first_upper) &&
2520
first_unmatched->last_inner != join_tab)
2522
join_tab->first_unmatched= first_unmatched;
2525
JoinTable *return_tab= join->return_tab;
2526
join_tab->found_match= true;
2529
It was not just a return to lower loop level when one
2530
of the newly activated predicates is evaluated as false
2531
(See above join->return_tab= tab).
2533
join->examined_rows++;
2534
join->session->row_count++;
2538
enum enum_nested_loop_state rc;
2539
/* A match from join_tab is found for the current partial join. */
2540
rc= (*join_tab->next_select)(join, join_tab+1, 0);
2541
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2543
if (return_tab < join->return_tab)
2544
join->return_tab= return_tab;
2546
if (join->return_tab < join_tab)
2547
return NESTED_LOOP_OK;
2549
Test if this was a SELECT DISTINCT query on a table that
2550
was not in the field list; In this case we can abort if
2551
we found a row, as no new rows can be added to the result.
2553
if (not_used_in_distinct && found_records != join->found_records)
2554
return NESTED_LOOP_NO_MORE_ROWS;
2557
join_tab->read_record.cursor->unlock_row();
2562
The condition pushed down to the table join_tab rejects all rows
2563
with the beginning coinciding with the current partial join.
2565
join->examined_rows++;
2566
join->session->row_count++;
2567
join_tab->read_record.cursor->unlock_row();
2569
return NESTED_LOOP_OK;
2574
Construct a NULL complimented partial join record and feed it to the next
2575
level of the nested loop. This function is used in case we have
2576
an OUTER join and no matching record was found.
2578
enum_nested_loop_state evaluate_null_complemented_join_record(JOIN *join, JoinTable *join_tab)
2581
The table join_tab is the first inner table of a outer join operation
2582
and no matches has been found for the current outer row.
2584
JoinTable *last_inner_tab= join_tab->last_inner;
2585
/* Cache variables for faster loop */
2587
for ( ; join_tab <= last_inner_tab ; join_tab++)
2589
/* Change the the values of guard predicate variables. */
2591
join_tab->not_null_compl= 0;
2592
/* The outer row is complemented by nulls for each inner tables */
2593
join_tab->table->restoreRecordAsDefault(); // Make empty record
2594
join_tab->table->mark_as_null_row(); // For group by without error
2595
select_cond= join_tab->select_cond;
2596
/* Check all attached conditions for inner table rows. */
2597
if (select_cond && !select_cond->val_int())
2598
return NESTED_LOOP_OK;
2602
The row complemented by nulls might be the first row
2603
of embedding outer joins.
2604
If so, perform the same actions as in the code
2605
for the first regular outer join row above.
2609
JoinTable *first_unmatched= join_tab->first_unmatched;
2610
if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
2612
join_tab->first_unmatched= first_unmatched;
2613
if (! first_unmatched)
2615
first_unmatched->found= 1;
2616
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2618
if (tab->select_cond && !tab->select_cond->val_int())
2620
join->return_tab= tab;
2621
return NESTED_LOOP_OK;
2626
The row complemented by nulls satisfies all conditions
2627
attached to inner tables.
2628
Send the row complemented by nulls to be joined with the
2631
return (*join_tab->next_select)(join, join_tab+1, 0);
2634
enum_nested_loop_state flush_cached_records(JOIN *join, JoinTable *join_tab, bool skip_last)
2636
enum_nested_loop_state rc= NESTED_LOOP_OK;
2640
join_tab->table->null_row= 0;
2641
if (!join_tab->cache.records)
2642
return NESTED_LOOP_OK; /* Nothing to do */
2644
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
2645
if (join_tab->use_quick == 2)
2647
if (join_tab->select->quick)
2648
{ /* Used quick select last. reset it */
2649
delete join_tab->select->quick;
2650
join_tab->select->quick=0;
2653
/* read through all records */
2654
if ((error=join_init_read_record(join_tab)))
2656
reset_cache_write(&join_tab->cache);
2657
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2660
for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)
2662
tmp->status=tmp->table->status;
2663
tmp->table->status=0;
2666
info= &join_tab->read_record;
2669
if (join->session->killed)
2671
join->session->send_kill_message();
2672
return NESTED_LOOP_KILLED;
2674
optimizer::SqlSelect *select= join_tab->select;
2675
if (rc == NESTED_LOOP_OK &&
2676
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2679
reset_cache_read(&join_tab->cache);
2680
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2682
join_tab->readCachedRecord();
2683
if (!select || !select->skip_record())
2687
rc= (join_tab->next_select)(join,join_tab+1,0);
2688
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2690
reset_cache_write(&join_tab->cache);
2695
return NESTED_LOOP_ERROR;
2699
} while (!(error=info->read_record(info)));
2702
join_tab->readCachedRecord(); // Restore current record
2703
reset_cache_write(&join_tab->cache);
2704
if (error > 0) // Fatal error
2705
return NESTED_LOOP_ERROR;
2706
for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2707
tmp2->table->status=tmp2->status;
2708
return NESTED_LOOP_OK;
2711
/*****************************************************************************
2713
Functions that end one nested loop iteration. Different functions
2714
are used to support GROUP BY clause and to redirect records
2715
to a table (e.g. in case of SELECT into a temporary table) or to the
2719
NESTED_LOOP_OK - the record has been successfully handled
2720
NESTED_LOOP_ERROR - a fatal error (like table corruption)
2722
NESTED_LOOP_KILLED - thread shutdown was requested while processing
2724
NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;
2725
additionally, the nested loop produced the
2726
number of rows specified in the LIMIT clause
2728
NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
2729
additionally, there is a cursor and the nested
2730
loop algorithm produced the number of rows
2731
that is specified for current cursor fetch
2733
All return values except NESTED_LOOP_OK abort the nested loop.
2734
*****************************************************************************/
2735
enum_nested_loop_state end_send(JOIN *join, JoinTable *, bool end_of_records)
2737
if (! end_of_records)
2740
if (join->having && join->having->val_int() == 0)
2741
return NESTED_LOOP_OK; // Didn't match having
2743
if (join->do_send_rows)
2744
error=join->result->send_data(*join->fields);
2746
return NESTED_LOOP_ERROR;
2747
if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2749
if (join->select_options & OPTION_FOUND_ROWS)
2751
JoinTable *jt=join->join_tab;
2752
if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2753
&& !join->send_group_parts && !join->having && !jt->select_cond &&
2754
!(jt->select && jt->select->quick) &&
2755
(jt->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
2758
/* Join over all rows in table; Return number of found rows */
2759
Table *table= jt->table;
2761
join->select_options^= OPTION_FOUND_ROWS;
2762
if (table->sort.record_pointers ||
2763
(table->sort.io_cache && my_b_inited(table->sort.io_cache)))
2765
/* Using filesort */
2766
join->send_records= table->sort.found_records;
2770
table->cursor->info(HA_STATUS_VARIABLE);
2771
join->send_records= table->cursor->stats.records;
2776
join->do_send_rows= 0;
2777
if (join->unit->fake_select_lex)
2778
join->unit->fake_select_lex->select_limit= 0;
2779
return NESTED_LOOP_OK;
2782
return NESTED_LOOP_QUERY_LIMIT; // Abort nicely
2784
else if (join->send_records >= join->fetch_limit)
2787
There is a server side cursor and all rows for
2788
this fetch request are sent.
2790
return NESTED_LOOP_CURSOR_LIMIT;
2794
return NESTED_LOOP_OK;
2797
enum_nested_loop_state end_write(JOIN *join, JoinTable *, bool end_of_records)
2799
Table *table= join->tmp_table;
2801
if (join->session->killed) // Aborted by user
2803
join->session->send_kill_message();
2804
return NESTED_LOOP_KILLED;
2806
if (!end_of_records)
2808
copy_fields(&join->tmp_table_param);
2809
copy_funcs(join->tmp_table_param.items_to_copy);
2810
if (!join->having || join->having->val_int())
2813
join->found_records++;
2814
if ((error=table->cursor->ha_write_row(table->record[0])))
2816
if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))
2818
if (create_myisam_from_heap(join->session, table,
2819
join->tmp_table_param.start_recinfo,
2820
&join->tmp_table_param.recinfo,
2822
return NESTED_LOOP_ERROR; // Not a table_is_full error
2823
table->s->uniques= 0; // To ensure rows are the same
2825
if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
2827
if (!(join->select_options & OPTION_FOUND_ROWS))
2828
return NESTED_LOOP_QUERY_LIMIT;
2829
join->do_send_rows= 0;
2830
join->unit->select_limit_cnt= HA_POS_ERROR;
2831
return NESTED_LOOP_OK;
2836
return NESTED_LOOP_OK;
2839
/** Group by searching after group record and updating it if possible. */
2840
enum_nested_loop_state end_update(JOIN *join, JoinTable *, bool end_of_records)
2842
Table *table= join->tmp_table;
2847
return NESTED_LOOP_OK;
2848
if (join->session->killed) // Aborted by user
2850
join->session->send_kill_message();
2851
return NESTED_LOOP_KILLED;
2854
join->found_records++;
2855
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2856
/* Make a key of group index */
2857
for (group=table->group ; group ; group=group->next)
2859
Item *item= *group->item;
2860
item->save_org_in_field(group->field);
2861
/* Store in the used key if the field was 0 */
2862
if (item->maybe_null)
2863
group->buff[-1]= (char) group->field->is_null();
2865
if (!table->cursor->index_read_map(table->record[1],
2866
join->tmp_table_param.group_buff,
2869
{ /* Update old record */
2870
table->restoreRecord();
2871
update_tmptable_sum_func(join->sum_funcs,table);
2872
if ((error= table->cursor->ha_update_row(table->record[1],
2875
table->print_error(error,MYF(0));
2876
return NESTED_LOOP_ERROR;
2878
return NESTED_LOOP_OK;
2882
Copy null bits from group key to table
2883
We can't copy all data as the key may have different format
2884
as the row data (for example as with VARCHAR keys)
2886
KEY_PART_INFO *key_part;
2887
for (group=table->group,key_part=table->key_info[0].key_part;
2889
group=group->next,key_part++)
2891
if (key_part->null_bit)
2892
memcpy(table->record[0]+key_part->offset, group->buff, 1);
2894
init_tmptable_sum_functions(join->sum_funcs);
2895
copy_funcs(join->tmp_table_param.items_to_copy);
2896
if ((error=table->cursor->ha_write_row(table->record[0])))
2898
if (create_myisam_from_heap(join->session, table,
2899
join->tmp_table_param.start_recinfo,
2900
&join->tmp_table_param.recinfo,
2902
return NESTED_LOOP_ERROR; // Not a table_is_full error
2903
/* Change method to update rows */
2904
table->cursor->ha_index_init(0, 0);
2905
join->join_tab[join->tables-1].next_select= end_unique_update;
2907
join->send_records++;
2908
return NESTED_LOOP_OK;
2911
/** Like end_update, but this is done with unique constraints instead of keys. */
2912
enum_nested_loop_state end_unique_update(JOIN *join, JoinTable *, bool end_of_records)
2914
Table *table= join->tmp_table;
2918
return NESTED_LOOP_OK;
2919
if (join->session->killed) // Aborted by user
2921
join->session->send_kill_message();
2922
return NESTED_LOOP_KILLED;
2925
init_tmptable_sum_functions(join->sum_funcs);
2926
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2927
copy_funcs(join->tmp_table_param.items_to_copy);
2929
if (!(error= table->cursor->ha_write_row(table->record[0])))
2930
join->send_records++; // New group
2933
if ((int) table->get_dup_key(error) < 0)
2935
table->print_error(error,MYF(0));
2936
return NESTED_LOOP_ERROR;
2938
if (table->cursor->rnd_pos(table->record[1],table->cursor->dup_ref))
2940
table->print_error(error,MYF(0));
2941
return NESTED_LOOP_ERROR;
2943
table->restoreRecord();
2944
update_tmptable_sum_func(join->sum_funcs,table);
2945
if ((error= table->cursor->ha_update_row(table->record[1],
2948
table->print_error(error,MYF(0));
2949
return NESTED_LOOP_ERROR;
2952
return NESTED_LOOP_OK;
2956
allocate group fields or take prepared (cached).
2958
@param main_join join of current select
2959
@param curr_join current join (join of current select or temporary copy
2967
static bool make_group_fields(JOIN *main_join, JOIN *curr_join)
2969
if (main_join->group_fields_cache.elements)
2971
curr_join->group_fields= main_join->group_fields_cache;
2972
curr_join->sort_and_group= 1;
2976
if (alloc_group_fields(curr_join, curr_join->group_list))
2978
main_join->group_fields_cache= curr_join->group_fields;
2984
calc how big buffer we need for comparing group entries.
2986
static void calc_group_buffer(JOIN *join,order_st *group)
2988
uint32_t key_length=0, parts=0, null_parts=0;
2992
for (; group ; group=group->next)
2994
Item *group_item= *group->item;
2995
Field *field= group_item->get_tmp_table_field();
2998
enum_field_types type;
2999
if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
3000
key_length+=MAX_BLOB_WIDTH; // Can't be used as a key
3001
else if (type == DRIZZLE_TYPE_VARCHAR)
3002
key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
3004
key_length+= field->pack_length();
3008
switch (group_item->result_type()) {
3010
key_length+= sizeof(double);
3013
key_length+= sizeof(int64_t);
3015
case DECIMAL_RESULT:
3016
key_length+= my_decimal_get_binary_size(group_item->max_length -
3017
(group_item->decimals ? 1 : 0),
3018
group_item->decimals);
3022
enum enum_field_types type= group_item->field_type();
3024
As items represented as DATE/TIME fields in the group buffer
3025
have STRING_RESULT result type, we increase the length
3026
by 8 as maximum pack length of such fields.
3028
if (type == DRIZZLE_TYPE_DATE ||
3029
type == DRIZZLE_TYPE_DATETIME ||
3030
type == DRIZZLE_TYPE_TIMESTAMP)
3037
Group strings are taken as varstrings and require an length field.
3038
A field is not yet created by create_tmp_field()
3039
and the sizes should match up.
3041
key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3046
/* This case should never be choosen */
3048
my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
3052
if (group_item->maybe_null)
3055
join->tmp_table_param.group_length=key_length+null_parts;
3056
join->tmp_table_param.group_parts=parts;
3057
join->tmp_table_param.group_null_parts=null_parts;
3061
Get a list of buffers for saveing last group.
3063
Groups are saved in reverse order for easyer check loop.
3065
static bool alloc_group_fields(JOIN *join,order_st *group)
3069
for (; group ; group=group->next)
3071
Cached_item *tmp= new_Cached_item(join->session, *group->item);
3072
if (!tmp || join->group_fields.push_front(tmp))
3076
join->sort_and_group=1; /* Mark for do_select */
3080
static uint32_t cache_record_length(JOIN *join,uint32_t idx)
3083
JoinTable **pos,**end;
3084
Session *session=join->session;
3086
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
3090
JoinTable *join_tab= *pos;
3091
if (!join_tab->used_fieldlength) /* Not calced yet */
3092
calc_used_field_length(session, join_tab);
3093
length+=join_tab->used_fieldlength;
3099
Get the number of different row combinations for subset of partial join
3103
join The join structure
3104
idx Number of tables in the partial join order (i.e. the
3105
partial join order is in join->positions[0..idx-1])
3106
found_ref Bitmap of tables for which we need to find # of distinct
3110
Given a partial join order (in join->positions[0..idx-1]) and a subset of
3111
tables within that join order (specified in found_ref), find out how many
3112
distinct row combinations of subset tables will be in the result of the
3115
This is used as follows: Suppose we have a table accessed with a ref-based
3116
method. The ref access depends on current rows of tables in found_ref.
3117
We want to count # of different ref accesses. We assume two ref accesses
3118
will be different if at least one of access parameters is different.
3119
Example: consider a query
3121
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
3124
t1, ref access on t1.key=c1
3125
t2, ref access on t2.key=c2
3126
t3, ref access on t3.key=t1.field
3128
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
3129
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
3130
For t3: n_ref_scans = records_read(t1)*records_read(t2)
3131
n_distinct_ref_scans = #records_read(t1)
3133
The reason for having this function (at least the latest version of it)
3134
is that we need to account for buffering in join execution.
3136
An edge-case example: if we have a non-first table in join accessed via
3137
ref(const) or ref(param) where there is a small number of different
3138
values of param, then the access will likely hit the disk cache and will
3139
not require any disk seeks.
3141
The proper solution would be to assume an LRU disk cache of some size,
3142
calculate probability of cache hits, etc. For now we just count
3143
identical ref accesses as one.
3146
Expected number of row combinations
3148
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
3151
optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3152
for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1);
3156
if (pos->examinePosition(found_ref))
3158
found_ref|= pos->getRefDependMap();
3160
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
3161
with no matching row we will get position[t2].records_read==0.
3162
Actually the size of output is one null-complemented row, therefore
3163
we will use value of 1 whenever we get records_read==0.
3166
- the above case can't occur if inner part of outer join has more
3167
than one table: table with no matches will not be marked as const.
3169
- Ideally we should add 1 to records_read for every possible null-
3170
complemented row. We're not doing it because: 1. it will require
3171
non-trivial code and add overhead. 2. The value of records_read
3172
is an inprecise estimate and adding 1 (or, in the worst case,
3173
#max_nested_outer_joins=64-1) will not make it any more precise.
3175
if (pos->getFanout() > DBL_EPSILON)
3176
found*= pos->getFanout();
3183
Set up join struct according to best position.
3185
static bool get_best_combination(JOIN *join)
3188
table_map used_tables;
3189
JoinTable *join_tab,*j;
3190
optimizer::KeyUse *keyuse;
3191
uint32_t table_count;
3192
Session *session=join->session;
3193
optimizer::Position cur_pos;
3195
table_count=join->tables;
3196
if (!(join->join_tab=join_tab=
3197
(JoinTable*) session->alloc(sizeof(JoinTable)*table_count)))
3202
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
3203
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
3206
cur_pos= join->getPosFromOptimalPlan(tablenr);
3207
*j= *cur_pos.getJoinTable();
3208
form=join->table[tablenr]=j->table;
3209
used_tables|= form->map;
3210
form->reginfo.join_tab=j;
3211
if (!*j->on_expr_ref)
3212
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
3213
if (j->type == AM_CONST)
3214
continue; // Handled in make_join_stat..
3219
if (j->type == AM_SYSTEM)
3221
if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
3224
if (tablenr != join->const_tables)
3227
else if (create_ref_for_key(join, j, keyuse, used_tables))
3228
return(true); // Something went wrong
3231
for (i=0 ; i < table_count ; i++)
3232
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
3233
update_depend_map(join);
3237
/** Save const tables first as used tables. */
3238
static void set_position(JOIN *join,
3241
optimizer::KeyUse *key)
3243
optimizer::Position tmp_pos(1.0, /* This is a const table */
3248
join->setPosInPartialPlan(idx, tmp_pos);
3250
/* Move the const table as down as possible in best_ref */
3251
JoinTable **pos=join->best_ref+idx+1;
3252
JoinTable *next=join->best_ref[idx];
3253
for (;next != table ; pos++)
3255
JoinTable *tmp=pos[0];
3259
join->best_ref[idx]=table;
3263
Selects and invokes a search strategy for an optimal query plan.
3265
The function checks user-configurable parameters that control the search
3266
strategy for an optimal plan, selects the search method and then invokes
3267
it. Each specific optimization procedure stores the final optimal plan in
3268
the array 'join->best_positions', and the cost of the plan in
3271
@param join pointer to the structure providing all context info for
3273
@param join_tables set of the tables in the query
3280
static bool choose_plan(JOIN *join, table_map join_tables)
3282
uint32_t search_depth= join->session->variables.optimizer_search_depth;
3283
uint32_t prune_level= join->session->variables.optimizer_prune_level;
3284
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
3286
join->cur_embedding_map.reset();
3287
reset_nj_counters(join->join_list);
3289
if (SELECT_STRAIGHT_JOIN option is set)
3290
reorder tables so dependent tables come after tables they depend
3291
on, otherwise keep tables in the order they were specified in the query
3293
Apply heuristic: pre-sort all access plans with respect to the number of
3296
internal::my_qsort(join->best_ref + join->const_tables,
3297
join->tables - join->const_tables, sizeof(JoinTable*),
3298
straight_join ? join_tab_cmp_straight : join_tab_cmp);
3301
optimize_straight_join(join, join_tables);
3305
if (search_depth == 0)
3306
/* Automatically determine a reasonable value for 'search_depth' */
3307
search_depth= determine_search_depth(join);
3308
if (greedy_search(join, join_tables, search_depth, prune_level))
3313
Store the cost of this query into a user variable
3314
Don't update last_query_cost for statements that are not "flat joins" :
3315
i.e. they have subqueries, unions or call stored procedures.
3316
TODO: calculate a correct cost for a query with subqueries and UNIONs.
3318
if (join->session->lex->is_single_level_stmt())
3319
join->session->status_var.last_query_cost= join->best_read;
3324
Find the best access path for an extension of a partial execution
3325
plan and add this path to the plan.
3327
The function finds the best access path to table 's' from the passed
3328
partial plan where an access path is the general term for any means to
3329
access the data in 's'. An access path may use either an index or a scan,
3330
whichever is cheaper. The input partial plan is passed via the array
3331
'join->positions' of length 'idx'. The chosen access method for 's' and its
3332
cost are stored in 'join->positions[idx]'.
3334
@param join pointer to the structure providing all context info
3336
@param s the table to be joined by the function
3337
@param session thread for the connection that submitted the query
3338
@param remaining_tables set of tables not included into the partial plan yet
3339
@param idx the length of the partial plan
3340
@param record_count estimate for the number of records returned by the
3342
@param read_time the cost of the partial plan
3347
static void best_access_path(JOIN *join,
3350
table_map remaining_tables,
3352
double record_count,
3355
optimizer::KeyUse *best_key= NULL;
3356
uint32_t best_max_key_part= 0;
3357
bool found_constraint= 0;
3358
double best= DBL_MAX;
3359
double best_time= DBL_MAX;
3360
double records= DBL_MAX;
3361
table_map best_ref_depends_map= 0;
3366
{ /* Use key if possible */
3367
Table *table= s->table;
3368
optimizer::KeyUse *keyuse= NULL;
3369
optimizer::KeyUse *start_key= NULL;
3370
double best_records= DBL_MAX;
3371
uint32_t max_key_part=0;
3373
/* Test how we can use keys */
3374
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
3375
for (keyuse= s->keyuse; keyuse->getTable() == table; )
3377
key_part_map found_part= 0;
3378
table_map found_ref= 0;
3379
uint32_t key= keyuse->getKey();
3380
KEY *keyinfo= table->key_info + key;
3381
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
3382
key_part_map const_part= 0;
3383
/* The or-null keypart in ref-or-null access: */
3384
key_part_map ref_or_null_part= 0;
3386
/* Calculate how many key segments of the current key we can use */
3389
do /* For each keypart */
3391
uint32_t keypart= keyuse->getKeypart();
3392
table_map best_part_found_ref= 0;
3393
double best_prev_record_reads= DBL_MAX;
3395
do /* For each way to access the keypart */
3399
if 1. expression doesn't refer to forward tables
3400
2. we won't get two ref-or-null's
3402
if (! (remaining_tables & keyuse->getUsedTables()) &&
3403
! (ref_or_null_part && (keyuse->getOptimizeFlags() &
3404
KEY_OPTIMIZE_REF_OR_NULL)))
3406
found_part|= keyuse->getKeypartMap();
3407
if (! (keyuse->getUsedTables() & ~join->const_table_map))
3408
const_part|= keyuse->getKeypartMap();
3410
double tmp2= prev_record_reads(join, idx, (found_ref |
3411
keyuse->getUsedTables()));
3412
if (tmp2 < best_prev_record_reads)
3414
best_part_found_ref= keyuse->getUsedTables() & ~join->const_table_map;
3415
best_prev_record_reads= tmp2;
3417
if (rec > keyuse->getTableRows())
3418
rec= keyuse->getTableRows();
3420
If there is one 'key_column IS NULL' expression, we can
3421
use this ref_or_null optimisation of this field
3423
if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)
3424
ref_or_null_part|= keyuse->getKeypartMap();
3428
} while (keyuse->getTable() == table && keyuse->getKey() == key &&
3429
keyuse->getKeypart() == keypart);
3430
found_ref|= best_part_found_ref;
3431
} while (keyuse->getTable() == table && keyuse->getKey() == key);
3434
Assume that that each key matches a proportional part of table.
3437
continue; // Nothing usable found
3439
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
3440
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
3443
found_constraint= 1;
3446
Check if we found full key
3448
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
3451
max_key_part= UINT32_MAX;
3452
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
3454
tmp = prev_record_reads(join, idx, found_ref);
3460
{ /* We found a const key */
3462
ReuseRangeEstimateForRef-1:
3463
We get here if we've found a ref(const) (c_i are constants):
3464
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
3466
If range optimizer was able to construct a "range"
3467
access on this index, then its condition "quick_cond" was
3468
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
3469
from the range optimizer.
3471
Proof of (*): By properties of range and ref optimizers
3472
quick_cond will be equal or tighther than ref_const_cond.
3473
ref_const_cond already covers "smallest" possible interval -
3474
a singlepoint interval over all keyparts. Therefore,
3475
quick_cond is equivalent to ref_const_cond (if it was an
3476
empty interval we wouldn't have got here).
3478
if (table->quick_keys.test(key))
3479
records= (double) table->quick_rows[key];
3482
/* quick_range couldn't use key! */
3483
records= (double) s->records/rec;
3488
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
3489
{ /* Prefer longer keys */
3491
((double) s->records / (double) rec *
3493
((double) (table->s->max_key_length-keyinfo->key_length) /
3494
(double) table->s->max_key_length)));
3496
records=2.0; /* Can't be as good as a unique */
3499
ReuseRangeEstimateForRef-2: We get here if we could not reuse
3500
E(#rows) from range optimizer. Make another try:
3502
If range optimizer produced E(#rows) for a prefix of the ref
3503
access we're considering, and that E(#rows) is lower then our
3504
current estimate, make an adjustment. The criteria of when we
3505
can make an adjustment is a special case of the criteria used
3506
in ReuseRangeEstimateForRef-3.
3508
if (table->quick_keys.test(key) &&
3509
const_part & (1 << table->quick_key_parts[key]) &&
3510
table->quick_n_ranges[key] == 1 &&
3511
records > (double) table->quick_rows[key])
3513
records= (double) table->quick_rows[key];
3516
/* Limit the number of matched rows */
3518
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3519
if (table->covering_keys.test(key))
3521
/* we can use only index tree */
3522
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3525
tmp= record_count * min(tmp,s->worst_seeks);
3531
Use as much key-parts as possible and a uniq key is better
3532
than a not unique key
3533
Set tmp to (previous record count) * (records / combination)
3535
if ((found_part & 1) &&
3536
(!(table->index_flags(key) & HA_ONLY_WHOLE_INDEX) ||
3537
found_part == PREV_BITS(uint, keyinfo->key_parts)))
3539
max_key_part= max_part_bit(found_part);
3541
ReuseRangeEstimateForRef-3:
3542
We're now considering a ref[or_null] access via
3543
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
3544
(same-as-above but with one cond replaced
3545
with "t.keypart_i IS NULL")] (**)
3547
Try re-using E(#rows) from "range" optimizer:
3548
We can do so if "range" optimizer used the same intervals as
3549
in (**). The intervals used by range optimizer may be not
3550
available at this point (as "range" access might have choosen to
3551
create quick select over another index), so we can't compare
3552
them to (**). We'll make indirect judgements instead.
3553
The sufficient conditions for re-use are:
3554
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
3555
this is not satisfied we have no way to know which ranges
3556
will be actually scanned by 'ref' until we execute the
3558
(C2) max #key parts in 'range' access == K == max_key_part (this
3559
is apparently a necessary requirement)
3561
We also have a property that "range optimizer produces equal or
3562
tighter set of scan intervals than ref(const) optimizer". Each
3563
of the intervals in (**) are "tightest possible" intervals when
3564
one limits itself to using keyparts 1..K (which we do in #2).
3565
From here it follows that range access used either one, or
3566
both of the (I1) and (I2) intervals:
3568
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
3569
(same-as-above but with one cond replaced
3570
with "t.keypart_i IS NULL") (I2)
3572
The remaining part is to exclude the situation where range
3573
optimizer used one interval while we're considering
3574
ref-or-null and looking for estimate for two intervals. This
3575
is done by last limitation:
3577
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
3579
if (table->quick_keys.test(key) && !found_ref && //(C1)
3580
table->quick_key_parts[key] == max_key_part && //(C2)
3581
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
3583
tmp= records= (double) table->quick_rows[key];
3587
/* Check if we have statistic about the distribution */
3588
if ((records= keyinfo->rec_per_key[max_key_part-1]))
3591
Fix for the case where the index statistics is too
3593
(1) We're considering ref(const) and there is quick select
3595
(2) and that quick select uses more keyparts (i.e. it will
3596
scan equal/smaller interval then this ref(const))
3597
(3) and E(#rows) for quick select is higher then our
3600
We'll use E(#rows) from quick select.
3602
Q: Why do we choose to use 'ref'? Won't quick select be
3603
cheaper in some cases ?
3604
TODO: figure this out and adjust the plan choice if needed.
3606
if (!found_ref && table->quick_keys.test(key) && // (1)
3607
table->quick_key_parts[key] > max_key_part && // (2)
3608
records < (double)table->quick_rows[key]) // (3)
3609
records= (double)table->quick_rows[key];
3616
Assume that the first key part matches 1% of the cursor
3617
and that the whole key matches 10 (duplicates) or 1
3619
Assume also that more key matches proportionally more
3621
This gives the formula:
3622
records = (x * (b-a) + a*c-b)/(c-1)
3624
b = records matched by whole key
3625
a = records matched by first key part (1% of all records?)
3626
c = number of key parts in key
3627
x = used key parts (1 <= x <= c)
3630
if (!(rec_per_key=(double)
3631
keyinfo->rec_per_key[keyinfo->key_parts-1]))
3632
rec_per_key=(double) s->records/rec+1;
3636
else if (rec_per_key/(double) s->records >= 0.01)
3640
double a=s->records*0.01;
3641
if (keyinfo->key_parts > 1)
3642
tmp= (max_key_part * (rec_per_key - a) +
3643
a*keyinfo->key_parts - rec_per_key)/
3644
(keyinfo->key_parts-1);
3647
set_if_bigger(tmp,1.0);
3649
records = (uint32_t) tmp;
3652
if (ref_or_null_part)
3654
/* We need to do two key searches to find key */
3660
ReuseRangeEstimateForRef-4: We get here if we could not reuse
3661
E(#rows) from range optimizer. Make another try:
3663
If range optimizer produced E(#rows) for a prefix of the ref
3664
access we're considering, and that E(#rows) is lower then our
3665
current estimate, make the adjustment.
3667
The decision whether we can re-use the estimate from the range
3668
optimizer is the same as in ReuseRangeEstimateForRef-3,
3669
applied to first table->quick_key_parts[key] key parts.
3671
if (table->quick_keys.test(key) &&
3672
table->quick_key_parts[key] <= max_key_part &&
3673
const_part & (1 << table->quick_key_parts[key]) &&
3674
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
3675
const_part) ? 1 : 0) &&
3676
records > (double) table->quick_rows[key])
3678
tmp= records= (double) table->quick_rows[key];
3682
/* Limit the number of matched rows */
3683
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3684
if (table->covering_keys.test(key))
3686
/* we can use only index tree */
3687
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3690
tmp= record_count * min(tmp,s->worst_seeks);
3693
tmp= best_time; // Do nothing
3697
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
3699
best_time= tmp + records/(double) TIME_FOR_COMPARE;
3701
best_records= records;
3702
best_key= start_key;
3703
best_max_key_part= max_key_part;
3704
best_ref_depends_map= found_ref;
3707
records= best_records;
3711
Don't test table scan if it can't be better.
3712
Prefer key lookup if we would use the same key for scanning.
3714
Don't do a table scan on InnoDB tables, if we can read the used
3715
parts of the row from any of the used index.
3716
This is because table scans uses index and we would not win
3717
anything by using a table scan.
3719
A word for word translation of the below if-statement in sergefp's
3720
understanding: we check if we should use table scan if:
3721
(1) The found 'ref' access produces more records than a table scan
3722
(or index scan, or quick select), or 'ref' is more expensive than
3724
(2) This doesn't hold: the best way to perform table scan is to to perform
3725
'range' access using index IDX, and the best way to perform 'ref'
3726
access is to use the same index IDX, with the same or more key parts.
3727
(note: it is not clear how this rule is/should be extended to
3728
index_merge quick selects)
3729
(3) See above note about InnoDB.
3730
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
3731
path, but there is no quick select)
3732
If the condition in the above brackets holds, then the only possible
3733
"table scan" access method is ALL/index (there is no quick select).
3734
Since we have a 'ref' access path, and FORCE INDEX instructs us to
3735
choose it over ALL/index, there is no need to consider a full table
3738
if ((records >= s->found_records || best > s->read_time) && // (1)
3739
! (s->quick && best_key && s->quick->index == best_key->getKey() && // (2)
3740
best_max_key_part >= s->table->quick_key_parts[best_key->getKey()]) &&// (2)
3741
! ((s->table->cursor->getEngine()->check_flag(HTON_BIT_TABLE_SCAN_ON_INDEX)) && // (3)
3742
! s->table->covering_keys.none() && best_key && !s->quick) && // (3)
3743
! (s->table->force_index && best_key && !s->quick)) // (4)
3744
{ // Check full join
3745
ha_rows rnd_records= s->found_records;
3747
If there is a filtering condition on the table (i.e. ref analyzer found
3748
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
3749
preceding this table in the join order we're now considering), then
3750
assume that 25% of the rows will be filtered out by this condition.
3752
This heuristic is supposed to force tables used in exprZ to be before
3753
this table in join order.
3755
if (found_constraint)
3756
rnd_records-= rnd_records/4;
3759
If applicable, get a more accurate estimate. Don't use the two
3762
if (s->table->quick_condition_rows != s->found_records)
3763
rnd_records= s->table->quick_condition_rows;
3766
Range optimizer never proposes a RANGE if it isn't better
3767
than FULL: so if RANGE is present, it's always preferred to FULL.
3768
Here we estimate its cost.
3774
- read record range through 'quick'
3775
- skip rows which does not satisfy WHERE constraints
3777
We take into account possible use of join cache for ALL/index
3778
access (see first else-branch below), but we don't take it into
3779
account here for range/index_merge access. Find out why this is so.
3782
(s->quick->read_time +
3783
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
3787
/* Estimate cost of reading table. */
3788
tmp= s->table->cursor->scan_time();
3789
if (s->table->map & join->outer_join) // Can't use join cache
3792
For each record we have to:
3793
- read the whole table record
3794
- skip rows which does not satisfy join condition
3798
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
3802
/* We read the table as many times as join buffer becomes full. */
3803
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
3805
(double) session->variables.join_buff_size));
3807
We don't make full cartesian product between rows in the scanned
3808
table and existing records because we skip all rows from the
3809
scanned table, which does not satisfy join condition when
3810
we read the table (see flush_cached_records for details). Here we
3811
take into account cost to read and skip these records.
3813
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
3818
We estimate the cost of evaluating WHERE clause for found records
3819
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
3820
tmp give us total cost of using Table SCAN
3822
if (best == DBL_MAX ||
3823
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
3824
best + record_count/(double) TIME_FOR_COMPARE*records))
3827
If the table has a range (s->quick is set) make_join_select()
3828
will ensure that this will be used
3831
records= rows2double(rnd_records);
3833
/* range/index_merge/ALL/index access method are "independent", so: */
3834
best_ref_depends_map= 0;
3838
/* Update the cost information for the current partial plan */
3839
optimizer::Position tmp_pos(records,
3843
best_ref_depends_map);
3844
join->setPosInPartialPlan(idx, tmp_pos);
3847
idx == join->const_tables &&
3848
s->table == join->sort_by_table &&
3849
join->unit->select_limit_cnt >= records)
3850
join->sort_by_table= (Table*) 1; // Must use temporary table
3856
Select the best ways to access the tables in a query without reordering them.
3858
Find the best access paths for each query table and compute their costs
3859
according to their order in the array 'join->best_ref' (thus without
3860
reordering the join tables). The function calls sequentially
3861
'best_access_path' for each table in the query to select the best table
3862
access method. The final optimal plan is stored in the array
3863
'join->best_positions', and the corresponding cost in 'join->best_read'.
3865
@param join pointer to the structure providing all context info for
3867
@param join_tables set of the tables in the query
3870
This function can be applied to:
3871
- queries with STRAIGHT_JOIN
3872
- internally to compute the cost of an arbitrary QEP
3874
Thus 'optimize_straight_join' can be used at any stage of the query
3875
optimization process to finalize a QEP as it is.
3877
static void optimize_straight_join(JOIN *join, table_map join_tables)
3880
optimizer::Position partial_pos;
3881
uint32_t idx= join->const_tables;
3882
double record_count= 1.0;
3883
double read_time= 0.0;
3885
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
3887
/* Find the best access method from 's' to the current partial plan */
3888
best_access_path(join, s, join->session, join_tables, idx,
3889
record_count, read_time);
3890
/* compute the cost of the new plan extended with 's' */
3891
partial_pos= join->getPosFromPartialPlan(idx);
3892
record_count*= partial_pos.getFanout();
3893
read_time+= partial_pos.getCost();
3894
join_tables&= ~(s->table->map);
3898
read_time+= record_count / (double) TIME_FOR_COMPARE;
3899
partial_pos= join->getPosFromPartialPlan(join->const_tables);
3900
if (join->sort_by_table &&
3901
partial_pos.hasTableForSorting(join->sort_by_table))
3902
read_time+= record_count; // We have to make a temp table
3903
join->copyPartialPlanIntoOptimalPlan(idx);
3904
join->best_read= read_time;
3908
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
3910
The search procedure uses a hybrid greedy/exhaustive search with controlled
3911
exhaustiveness. The search is performed in N = card(remaining_tables)
3912
steps. Each step evaluates how promising is each of the unoptimized tables,
3913
selects the most promising table, and extends the current partial QEP with
3914
that table. Currenly the most 'promising' table is the one with least
3915
expensive extension.\
3917
There are two extreme cases:
3918
-# When (card(remaining_tables) < search_depth), the estimate finds the
3919
best complete continuation of the partial QEP. This continuation can be
3920
used directly as a result of the search.
3921
-# When (search_depth == 1) the 'best_extension_by_limited_search'
3922
consideres the extension of the current QEP with each of the remaining
3925
All other cases are in-between these two extremes. Thus the parameter
3926
'search_depth' controlls the exhaustiveness of the search. The higher the
3927
value, the longer the optimizaton time and possibly the better the
3928
resulting plan. The lower the value, the fewer alternative plans are
3929
estimated, but the more likely to get a bad QEP.
3931
All intermediate and final results of the procedure are stored in 'join':
3932
- join->positions : modified for every partial QEP that is explored
3933
- join->best_positions: modified for the current best complete QEP
3934
- join->best_read : modified for the current best complete QEP
3935
- join->best_ref : might be partially reordered
3937
The final optimal plan is stored in 'join->best_positions', and its
3938
corresponding cost in 'join->best_read'.
3941
The following pseudocode describes the algorithm of 'greedy_search':
3944
procedure greedy_search
3945
input: remaining_tables
3950
(t, a) = best_extension(pplan, remaining_tables);
3951
pplan = concat(pplan, (t, a));
3952
remaining_tables = remaining_tables - t;
3953
} while (remaining_tables != {})
3958
where 'best_extension' is a placeholder for a procedure that selects the
3959
most "promising" of all tables in 'remaining_tables'.
3960
Currently this estimate is performed by calling
3961
'best_extension_by_limited_search' to evaluate all extensions of the
3962
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
3963
mainly depends on that of 'best_extension_by_limited_search'.
3966
If 'best_extension()' == 'best_extension_by_limited_search()', then the
3967
worst-case complexity of this algorithm is <=
3968
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
3969
complexity of greedy_search is O(N!).
3972
In the future, 'greedy_search' might be extended to support other
3973
implementations of 'best_extension', e.g. some simpler quadratic procedure.
3975
@param join pointer to the structure providing all context info
3977
@param remaining_tables set of tables not included into the partial plan yet
3978
@param search_depth controlls the exhaustiveness of the search
3979
@param prune_level the pruning heuristics that should be applied during
3987
static bool greedy_search(JOIN *join,
3988
table_map remaining_tables,
3989
uint32_t search_depth,
3990
uint32_t prune_level)
3992
double record_count= 1.0;
3993
double read_time= 0.0;
3994
uint32_t idx= join->const_tables; // index into 'join->best_ref'
3996
uint32_t size_remain; // cardinality of remaining_tables
3997
optimizer::Position best_pos;
3998
JoinTable *best_table; // the next plan node to be added to the curr QEP
4000
/* number of tables that remain to be optimized */
4001
size_remain= internal::my_count_bits(remaining_tables);
4004
/* Find the extension of the current QEP with the lowest cost */
4005
join->best_read= DBL_MAX;
4006
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
4007
read_time, search_depth, prune_level))
4010
if (size_remain <= search_depth)
4013
'join->best_positions' contains a complete optimal extension of the
4014
current partial QEP.
4019
/* select the first table in the optimal extension as most promising */
4020
best_pos= join->getPosFromOptimalPlan(idx);
4021
best_table= best_pos.getJoinTable();
4023
Each subsequent loop of 'best_extension_by_limited_search' uses
4024
'join->positions' for cost estimates, therefore we have to update its
4027
join->setPosInPartialPlan(idx, best_pos);
4029
/* find the position of 'best_table' in 'join->best_ref' */
4031
JoinTable *pos= join->best_ref[best_idx];
4032
while (pos && best_table != pos)
4033
pos= join->best_ref[++best_idx];
4034
assert((pos != NULL)); // should always find 'best_table'
4035
/* move 'best_table' at the first free position in the array of joins */
4036
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
4038
/* compute the cost of the new plan extended with 'best_table' */
4039
optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
4040
record_count*= partial_pos.getFanout();
4041
read_time+= partial_pos.getCost();
4043
remaining_tables&= ~(best_table->table->map);
4051
Find a good, possibly optimal, query execution plan (QEP) by a possibly
4054
The procedure searches for the optimal ordering of the query tables in set
4055
'remaining_tables' of size N, and the corresponding optimal access paths to
4056
each table. The choice of a table order and an access path for each table
4057
constitutes a query execution plan (QEP) that fully specifies how to
4060
The maximal size of the found plan is controlled by the parameter
4061
'search_depth'. When search_depth == N, the resulting plan is complete and
4062
can be used directly as a QEP. If search_depth < N, the found plan consists
4063
of only some of the query tables. Such "partial" optimal plans are useful
4064
only as input to query optimization procedures, and cannot be used directly
4067
The algorithm begins with an empty partial plan stored in 'join->positions'
4068
and a set of N tables - 'remaining_tables'. Each step of the algorithm
4069
evaluates the cost of the partial plan extended by all access plans for
4070
each of the relations in 'remaining_tables', expands the current partial
4071
plan with the access plan that results in lowest cost of the expanded
4072
partial plan, and removes the corresponding relation from
4073
'remaining_tables'. The algorithm continues until it either constructs a
4074
complete optimal plan, or constructs an optimal plartial plan with size =
4077
The final optimal plan is stored in 'join->best_positions'. The
4078
corresponding cost of the optimal plan is in 'join->best_read'.
4081
The procedure uses a recursive depth-first search where the depth of the
4082
recursion (and thus the exhaustiveness of the search) is controlled by the
4083
parameter 'search_depth'.
4086
The pseudocode below describes the algorithm of
4087
'best_extension_by_limited_search'. The worst-case complexity of this
4088
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
4089
the complexity of greedy_search is O(N!).
4092
procedure best_extension_by_limited_search(
4093
pplan in, // in, partial plan of tables-joined-so-far
4094
pplan_cost, // in, cost of pplan
4095
remaining_tables, // in, set of tables not referenced in pplan
4096
best_plan_so_far, // in/out, best plan found so far
4097
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
4098
search_depth) // in, maximum size of the plans being considered
4100
for each table T from remaining_tables
4102
// Calculate the cost of using table T as above
4103
cost = complex-series-of-calculations;
4105
// Add the cost to the cost so far.
4108
if (pplan_cost >= best_plan_so_far_cost)
4109
// pplan_cost already too great, stop search
4112
pplan= expand pplan by best_access_method;
4113
remaining_tables= remaining_tables - table T;
4114
if (remaining_tables is not an empty set
4118
best_extension_by_limited_search(pplan, pplan_cost,
4121
best_plan_so_far_cost,
4126
best_plan_so_far_cost= pplan_cost;
4127
best_plan_so_far= pplan;
4134
When 'best_extension_by_limited_search' is called for the first time,
4135
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
4136
The actual implementation provides a way to optionally use pruning
4137
heuristic (controlled by the parameter 'prune_level') to reduce the search
4138
space by skipping some partial plans.
4141
The parameter 'search_depth' provides control over the recursion
4142
depth, and thus the size of the resulting optimal plan.
4144
@param join pointer to the structure providing all context info
4146
@param remaining_tables set of tables not included into the partial plan yet
4147
@param idx length of the partial QEP in 'join->positions';
4148
since a depth-first search is used, also corresponds
4149
to the current depth of the search tree;
4150
also an index in the array 'join->best_ref';
4151
@param record_count estimate for the number of records returned by the
4153
@param read_time the cost of the best partial plan
4154
@param search_depth maximum depth of the recursion and thus size of the
4156
(0 < search_depth <= join->tables+1).
4157
@param prune_level pruning heuristics that should be applied during
4159
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
4166
static bool best_extension_by_limited_search(JOIN *join,
4167
table_map remaining_tables,
4169
double record_count,
4171
uint32_t search_depth,
4172
uint32_t prune_level)
4174
Session *session= join->session;
4175
if (session->killed) // Abort
4179
'join' is a partial plan with lower cost than the best plan so far,
4180
so continue expanding it further with the tables in 'remaining_tables'.
4183
double best_record_count= DBL_MAX;
4184
double best_read_time= DBL_MAX;
4185
optimizer::Position partial_pos;
4187
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4189
table_map real_table_bit= s->table->map;
4192
partial_pos= join->getPosFromPartialPlan(idx - 1);
4194
if ((remaining_tables & real_table_bit) &&
4195
! (remaining_tables & s->dependent) &&
4196
(! idx || ! check_interleaving_with_nj(partial_pos.getJoinTable(), s)))
4198
double current_record_count, current_read_time;
4201
psergey-insideout-todo:
4202
when best_access_path() detects it could do an InsideOut scan or
4203
some other scan, have it return an insideout scan and a flag that
4204
requests to "fork" this loop iteration. (Q: how does that behave
4205
when the depth is insufficient??)
4207
/* Find the best access method from 's' to the current partial plan */
4208
best_access_path(join, s, session, remaining_tables, idx,
4209
record_count, read_time);
4210
/* Compute the cost of extending the plan with 's' */
4211
partial_pos= join->getPosFromPartialPlan(idx);
4212
current_record_count= record_count * partial_pos.getFanout();
4213
current_read_time= read_time + partial_pos.getCost();
4215
/* Expand only partial plans with lower cost than the best QEP so far */
4216
if ((current_read_time +
4217
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
4219
restore_prev_nj_state(s);
4224
Prune some less promising partial plans. This heuristic may miss
4225
the optimal QEPs, thus it results in a non-exhaustive search.
4227
if (prune_level == 1)
4229
if (best_record_count > current_record_count ||
4230
best_read_time > current_read_time ||
4231
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
4233
if (best_record_count >= current_record_count &&
4234
best_read_time >= current_read_time &&
4235
/* TODO: What is the reasoning behind this condition? */
4236
(! (s->key_dependent & remaining_tables) ||
4237
partial_pos.isConstTable()))
4239
best_record_count= current_record_count;
4240
best_read_time= current_read_time;
4245
restore_prev_nj_state(s);
4250
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
4251
{ /* Recursively expand the current partial plan */
4252
std::swap(join->best_ref[idx], *pos);
4253
if (best_extension_by_limited_search(join,
4254
remaining_tables & ~real_table_bit,
4256
current_record_count,
4261
std::swap(join->best_ref[idx], *pos);
4265
'join' is either the best partial QEP with 'search_depth' relations,
4266
or the best complete QEP so far, whichever is smaller.
4268
partial_pos= join->getPosFromPartialPlan(join->const_tables);
4269
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4270
if (join->sort_by_table &&
4271
partial_pos.hasTableForSorting(join->sort_by_table))
4272
/* We have to make a temp table */
4273
current_read_time+= current_record_count;
4274
if ((search_depth == 1) || (current_read_time < join->best_read))
4276
join->copyPartialPlanIntoOptimalPlan(idx + 1);
4277
join->best_read= current_read_time - 0.001;
4280
restore_prev_nj_state(s);
4287
Heuristic procedure to automatically guess a reasonable degree of
4288
exhaustiveness for the greedy search procedure.
4290
The procedure estimates the optimization time and selects a search depth
4291
big enough to result in a near-optimal QEP, that doesn't take too long to
4292
find. If the number of tables in the query exceeds some constant, then
4293
search_depth is set to this constant.
4295
@param join pointer to the structure providing all context info for
4299
This is an extremely simplistic implementation that serves as a stub for a
4300
more advanced analysis of the join. Ideally the search depth should be
4301
determined by learning from previous query optimizations, because it will
4302
depend on the CPU power (and other factors).
4305
this value should be determined dynamically, based on statistics:
4306
uint32_t max_tables_for_exhaustive_opt= 7;
4309
this value could be determined by some mapping of the form:
4310
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4313
A positive integer that specifies the search depth (and thus the
4314
exhaustiveness) of the depth-first search algorithm used by
4317
static uint32_t determine_search_depth(JOIN *join)
4319
uint32_t table_count= join->tables - join->const_tables;
4320
uint32_t search_depth;
4321
/* TODO: this value should be determined dynamically, based on statistics: */
4322
uint32_t max_tables_for_exhaustive_opt= 7;
4324
if (table_count <= max_tables_for_exhaustive_opt)
4325
search_depth= table_count+1; // use exhaustive for small number of tables
4328
TODO: this value could be determined by some mapping of the form:
4329
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4331
search_depth= max_tables_for_exhaustive_opt; // use greedy search
4333
return search_depth;
4336
static bool make_simple_join(JOIN *join,Table *tmp_table)
4339
JoinTable *join_tab;
4342
Reuse Table * and JoinTable if already allocated by a previous call
4343
to this function through JOIN::exec (may happen for sub-queries).
4345
if (!join->table_reexec)
4347
if (!(join->table_reexec= (Table**) join->session->alloc(sizeof(Table*))))
4350
join->tmp_join->table_reexec= join->table_reexec;
4352
if (!join->join_tab_reexec)
4354
if (!(join->join_tab_reexec=
4355
(JoinTable*) join->session->alloc(sizeof(JoinTable))))
4358
join->tmp_join->join_tab_reexec= join->join_tab_reexec;
4360
tableptr= join->table_reexec;
4361
join_tab= join->join_tab_reexec;
4363
join->join_tab=join_tab;
4364
join->table=tableptr; tableptr[0]=tmp_table;
4366
join->const_tables=0;
4367
join->const_table_map=0;
4368
join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=
4369
join->tmp_table_param.func_count=0;
4370
join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;
4371
join->first_record=join->sort_and_group=0;
4372
join->send_records=(ha_rows) 0;
4374
join->row_limit=join->unit->select_limit_cnt;
4375
join->do_send_rows = (join->row_limit) ? 1 : 0;
4377
join_tab->cache.buff=0; /* No caching */
4378
join_tab->table=tmp_table;
4380
join_tab->select_cond=0;
4382
join_tab->type= AM_ALL; /* Map through all records */
4383
join_tab->keys.set(); /* test everything in quick */
4385
join_tab->on_expr_ref=0;
4386
join_tab->last_inner= 0;
4387
join_tab->first_unmatched= 0;
4388
join_tab->ref.key = -1;
4389
join_tab->not_used_in_distinct=0;
4390
join_tab->read_first_record= join_init_read_record;
4391
join_tab->join=join;
4392
join_tab->ref.key_parts= 0;
4393
memset(&join_tab->read_record, 0, sizeof(join_tab->read_record));
4394
tmp_table->status=0;
4395
tmp_table->null_row=0;
4400
Fill in outer join related info for the execution plan structure.
4402
For each outer join operation left after simplification of the
4403
original query the function set up the following pointers in the linear
4404
structure join->join_tab representing the selected execution plan.
4405
The first inner table t0 for the operation is set to refer to the last
4406
inner table tk through the field t0->last_inner.
4407
Any inner table ti for the operation are set to refer to the first
4408
inner table ti->first_inner.
4409
The first inner table t0 for the operation is set to refer to the
4410
first inner table of the embedding outer join operation, if there is any,
4411
through the field t0->first_upper.
4412
The on expression for the outer join operation is attached to the
4413
corresponding first inner table through the field t0->on_expr_ref.
4414
Here ti are structures of the JoinTable type.
4416
EXAMPLE. For the query:
4420
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
4421
ON (t1.a=t2.a AND t1.b=t3.b)
4425
given the execution plan with the table order t1,t2,t3,t4
4426
is selected, the following references will be set;
4427
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
4428
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
4429
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
4430
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
4432
@param join reference to the info fully describing the query
4435
The function assumes that the simplification procedure has been
4436
already applied to the join query (see simplify_joins).
4437
This function can be called only after the execution plan
4440
static void make_outerjoin_info(JOIN *join)
4442
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4444
JoinTable *tab=join->join_tab+i;
4445
Table *table=tab->table;
4446
TableList *tbl= table->pos_in_table_list;
4447
TableList *embedding= tbl->embedding;
4449
if (tbl->outer_join)
4452
Table tab is the only one inner table for outer join.
4453
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
4454
is in the query above.)
4456
tab->last_inner= tab->first_inner= tab;
4457
tab->on_expr_ref= &tbl->on_expr;
4458
tab->cond_equal= tbl->cond_equal;
4460
tab->first_upper= embedding->nested_join->first_nested;
4462
for ( ; embedding ; embedding= embedding->embedding)
4464
/* Ignore sj-nests: */
4465
if (!embedding->on_expr)
4467
nested_join_st *nested_join= embedding->nested_join;
4468
if (!nested_join->counter_)
4471
Table tab is the first inner table for nested_join.
4472
Save reference to it in the nested join structure.
4474
nested_join->first_nested= tab;
4475
tab->on_expr_ref= &embedding->on_expr;
4476
tab->cond_equal= tbl->cond_equal;
4477
if (embedding->embedding)
4478
tab->first_upper= embedding->embedding->nested_join->first_nested;
4480
if (!tab->first_inner)
4481
tab->first_inner= nested_join->first_nested;
4482
if (++nested_join->counter_ < nested_join->join_list.elements)
4484
/* Table tab is the last inner table for nested join. */
4485
nested_join->first_nested->last_inner= tab;
4491
static bool make_join_select(JOIN *join,
4492
optimizer::SqlSelect *select,
4495
Session *session= join->session;
4496
optimizer::Position cur_pos;
4499
add_not_null_conds(join);
4500
table_map used_tables;
4501
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
4502
{ /* there may be a select without a cond. */
4503
if (join->tables > 1)
4504
cond->update_used_tables(); // Tablenr may have changed
4505
if (join->const_tables == join->tables &&
4506
session->lex->current_select->master_unit() ==
4507
&session->lex->unit) // not upper level SELECT
4508
join->const_table_map|=RAND_TABLE_BIT;
4509
{ // Check const tables
4511
make_cond_for_table(cond,
4512
join->const_table_map,
4514
for (JoinTable *tab= join->join_tab+join->const_tables;
4515
tab < join->join_tab+join->tables ; tab++)
4517
if (*tab->on_expr_ref)
4519
JoinTable *cond_tab= tab->first_inner;
4520
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
4521
join->const_table_map,
4525
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4528
tmp->quick_fix_field();
4529
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4530
new Item_cond_and(cond_tab->select_cond,
4532
if (! cond_tab->select_cond)
4534
cond_tab->select_cond->quick_fix_field();
4537
if (const_cond && ! const_cond->val_int())
4539
return 1; // Impossible const condition
4543
used_tables=((select->const_tables=join->const_table_map) |
4544
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4545
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4547
JoinTable *tab=join->join_tab+i;
4549
first_inner is the X in queries like:
4550
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
4552
JoinTable *first_inner_tab= tab->first_inner;
4553
table_map current_map= tab->table->map;
4554
bool use_quick_range=0;
4558
Following force including random expression in last table condition.
4559
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
4561
if (i == join->tables-1)
4562
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
4563
used_tables|=current_map;
4565
if (tab->type == AM_REF && tab->quick &&
4566
(uint32_t) tab->ref.key == tab->quick->index &&
4567
tab->ref.key_length < tab->quick->max_used_key_length)
4569
/* Range uses longer key; Use this instead of ref on key */
4574
tab->ref.key_parts= 0; // Don't use ref key.
4575
cur_pos= join->getPosFromOptimalPlan(i);
4576
cur_pos.setFanout(rows2double(tab->quick->records));
4578
We will use join cache here : prevent sorting of the first
4579
table only and sort at the end.
4581
if (i != join->const_tables && join->tables > join->const_tables + 1)
4587
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
4588
if (cond && !tmp && tab->quick)
4590
if (tab->type != AM_ALL)
4593
Don't use the quick method
4594
We come here in the case where we have 'key=constant' and
4595
the test is removed by make_cond_for_table()
4603
Hack to handle the case where we only refer to a table
4604
in the ON part of an OUTER JOIN. In this case we want the code
4605
below to check if we should use 'quick' instead.
4607
tmp= new Item_int((int64_t) 1,1); // Always true
4611
if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||
4612
tab->type == AM_EQ_REF)
4614
optimizer::SqlSelect *sel= tab->select= ((optimizer::SqlSelect*)
4615
session->memdup((unsigned char*) select,
4618
return 1; // End of memory
4620
If tab is an inner table of an outer join operation,
4621
add a match guard to the pushed down predicate.
4622
The guard will turn the predicate on only after
4623
the first match for outer tables is encountered.
4628
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
4629
a cond, so neutralize the hack above.
4631
if (! (tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
4633
tab->select_cond=sel->cond=tmp;
4636
tab->select_cond= sel->cond= NULL;
4638
sel->head=tab->table;
4641
/* Use quick key read if it's a constant and it's not used
4643
if (tab->needed_reg.none() && tab->type != AM_EQ_REF
4644
&& (tab->type != AM_REF || (uint32_t) tab->ref.key == tab->quick->index))
4646
sel->quick=tab->quick; // Use value from get_quick_...
4647
sel->quick_keys.reset();
4648
sel->needed_reg.reset();
4656
uint32_t ref_key= static_cast<uint32_t>(sel->head->reginfo.join_tab->ref.key + 1);
4657
if (i == join->const_tables && ref_key)
4659
if (tab->const_keys.any() &&
4660
tab->table->reginfo.impossible_range)
4663
else if (tab->type == AM_ALL && ! use_quick_range)
4665
if (tab->const_keys.any() &&
4666
tab->table->reginfo.impossible_range)
4667
return 1; // Impossible range
4669
We plan to scan all rows.
4670
Check again if we should use an index.
4671
We could have used an column from a previous table in
4672
the index if we are using limit and this is the first table
4675
cur_pos= join->getPosFromOptimalPlan(i);
4676
if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
4677
(! tab->const_keys.none() && (i == join->const_tables) &&
4678
(join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4680
/* Join with outer join condition */
4681
COND *orig_cond= sel->cond;
4682
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
4685
We can't call sel->cond->fix_fields,
4686
as it will break tab->on_expr if it's AND condition
4687
(fix_fields currently removes extra AND/OR levels).
4688
Yet attributes of the just built condition are not needed.
4689
Thus we call sel->cond->quick_fix_field for safety.
4691
if (sel->cond && ! sel->cond->fixed)
4692
sel->cond->quick_fix_field();
4694
if (sel->test_quick_select(session, tab->keys,
4695
used_tables & ~ current_map,
4696
(join->select_options &
4699
join->unit->select_limit_cnt), 0,
4703
Before reporting "Impossible WHERE" for the whole query
4704
we have to check isn't it only "impossible ON" instead
4706
sel->cond=orig_cond;
4707
if (! *tab->on_expr_ref ||
4708
sel->test_quick_select(session, tab->keys,
4709
used_tables & ~ current_map,
4710
(join->select_options &
4713
join->unit->select_limit_cnt),0,
4715
return 1; // Impossible WHERE
4718
sel->cond=orig_cond;
4720
/* Fix for EXPLAIN */
4723
cur_pos= join->getPosFromOptimalPlan(i);
4724
cur_pos.setFanout(static_cast<double>(sel->quick->records));
4729
sel->needed_reg= tab->needed_reg;
4730
sel->quick_keys.reset();
4732
if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
4733
!((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
4735
tab->keys= sel->quick_keys;
4736
tab->keys|= sel->needed_reg;
4737
tab->use_quick= (!sel->needed_reg.none() &&
4738
(select->quick_keys.none() ||
4740
(select->quick->records >= 100L)))) ?
4742
sel->read_tables= used_tables & ~current_map;
4744
if (i != join->const_tables && tab->use_quick != 2)
4745
{ /* Read with cache */
4747
(tmp=make_cond_for_table(cond,
4748
join->const_table_map |
4752
tab->cache.select= (optimizer::SqlSelect*)
4753
session->memdup((unsigned char*) sel, sizeof(optimizer::SqlSelect));
4754
tab->cache.select->cond= tmp;
4755
tab->cache.select->read_tables= join->const_table_map;
4762
Push down conditions from all on expressions.
4763
Each of these conditions are guarded by a variable
4764
that turns if off just before null complemented row for
4765
outer joins is formed. Thus, the condition from an
4766
'on expression' are guaranteed not to be checked for
4767
the null complemented row.
4770
/* First push down constant conditions from on expressions */
4771
for (JoinTable *join_tab= join->join_tab+join->const_tables;
4772
join_tab < join->join_tab+join->tables ; join_tab++)
4774
if (*join_tab->on_expr_ref)
4776
JoinTable *cond_tab= join_tab->first_inner;
4777
tmp= make_cond_for_table(*join_tab->on_expr_ref,
4778
join->const_table_map,
4782
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4785
tmp->quick_fix_field();
4786
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4787
new Item_cond_and(cond_tab->select_cond,tmp);
4788
if (! cond_tab->select_cond)
4790
cond_tab->select_cond->quick_fix_field();
4794
/* Push down non-constant conditions from on expressions */
4795
JoinTable *last_tab= tab;
4796
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
4799
Table tab is the last inner table of an outer join.
4800
An on expression is always attached to it.
4802
COND *on_expr= *first_inner_tab->on_expr_ref;
4804
table_map used_tables2= (join->const_table_map |
4805
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4806
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
4808
current_map= tab->table->map;
4809
used_tables2|= current_map;
4810
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
4814
JoinTable *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
4816
First add the guards for match variables of
4817
all embedding outer join operations.
4819
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
4824
Now add the guard turning the predicate off for
4825
the null complemented row.
4827
tmp_cond= new Item_func_trig_cond(tmp_cond,
4831
tmp_cond->quick_fix_field();
4832
/* Add the predicate to other pushed down predicates */
4833
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
4834
new Item_cond_and(cond_tab->select_cond,
4836
if (! cond_tab->select_cond)
4838
cond_tab->select_cond->quick_fix_field();
4841
first_inner_tab= first_inner_tab->first_upper;
4849
Plan refinement stage: do various set ups for the executioner
4852
make_join_readinfo()
4853
join Join being processed
4854
options Join's options (checking for SELECT_DESCRIBE,
4855
SELECT_NO_JOIN_CACHE)
4856
no_jbuf_after Don't use join buffering after table with this number.
4859
Plan refinement stage: do various set ups for the executioner
4860
- set up use of join buffering
4861
- push index conditions
4862
- increment counters
4867
true - Out of memory
4869
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
4872
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
4875
for (i=join->const_tables ; i < join->tables ; i++)
4877
JoinTable *tab=join->join_tab+i;
4878
Table *table=tab->table;
4879
bool using_join_cache;
4880
tab->read_record.table= table;
4881
tab->read_record.cursor= table->cursor;
4882
tab->next_select=sub_select; /* normal select */
4884
TODO: don't always instruct first table's ref/range access method to
4885
produce sorted output.
4887
tab->sorted= sorted;
4888
sorted= 0; // only first must be sorted
4889
if (tab->insideout_match_tab)
4891
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
4896
switch (tab->type) {
4897
case AM_SYSTEM: // Only happens with left join
4898
table->status=STATUS_NO_RECORD;
4899
tab->read_first_record= join_read_system;
4900
tab->read_record.read_record= join_no_more_records;
4902
case AM_CONST: // Only happens with left join
4903
table->status=STATUS_NO_RECORD;
4904
tab->read_first_record= join_read_const;
4905
tab->read_record.read_record= join_no_more_records;
4906
if (table->covering_keys.test(tab->ref.key) &&
4910
table->cursor->extra(HA_EXTRA_KEYREAD);
4914
table->status=STATUS_NO_RECORD;
4917
delete tab->select->quick;
4918
tab->select->quick=0;
4922
tab->read_first_record= join_read_key;
4923
tab->read_record.read_record= join_no_more_records;
4924
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4927
table->cursor->extra(HA_EXTRA_KEYREAD);
4930
case AM_REF_OR_NULL:
4932
table->status=STATUS_NO_RECORD;
4935
delete tab->select->quick;
4936
tab->select->quick=0;
4940
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4943
table->cursor->extra(HA_EXTRA_KEYREAD);
4945
if (tab->type == AM_REF)
4947
tab->read_first_record= join_read_always_key;
4948
tab->read_record.read_record= tab->insideout_match_tab?
4949
join_read_next_same_diff : join_read_next_same;
4953
tab->read_first_record= join_read_always_key_or_null;
4954
tab->read_record.read_record= join_read_next_same_or_null;
4959
If previous table use cache
4960
If the incoming data set is already sorted don't use cache.
4962
table->status=STATUS_NO_RECORD;
4963
using_join_cache= false;
4964
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
4965
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
4966
!tab->insideout_match_tab)
4968
if ((options & SELECT_DESCRIBE) ||
4969
!join_init_cache(join->session,join->join_tab+join->const_tables,
4970
i-join->const_tables))
4972
using_join_cache= true;
4973
tab[-1].next_select=sub_select_cache; /* Patch previous */
4976
/* These init changes read_record */
4977
if (tab->use_quick == 2)
4979
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
4980
tab->read_first_record= join_init_quick_read_record;
4982
status_var_increment(join->session->status_var.select_range_check_count);
4986
tab->read_first_record= join_init_read_record;
4987
if (i == join->const_tables)
4989
if (tab->select && tab->select->quick)
4992
status_var_increment(join->session->status_var.select_range_count);
4996
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
4998
status_var_increment(join->session->status_var.select_scan_count);
5003
if (tab->select && tab->select->quick)
5006
status_var_increment(join->session->status_var.select_full_range_join_count);
5010
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
5012
status_var_increment(join->session->status_var.select_full_join_count);
5015
if (!table->no_keyread)
5017
if (tab->select && tab->select->quick &&
5018
tab->select->quick->index != MAX_KEY && //not index_merge
5019
table->covering_keys.test(tab->select->quick->index))
5022
table->cursor->extra(HA_EXTRA_KEYREAD);
5024
else if (!table->covering_keys.none() &&
5025
!(tab->select && tab->select->quick))
5026
{ // Only read index tree
5027
if (!tab->insideout_match_tab)
5030
See bug #26447: "Using the clustered index for a table scan
5031
is always faster than using a secondary index".
5033
if (table->s->primary_key != MAX_KEY &&
5034
table->cursor->primary_key_is_clustered())
5035
tab->index= table->s->primary_key;
5037
tab->index= table->find_shortest_key(&table->covering_keys);
5039
tab->read_first_record= join_read_first;
5040
tab->type= AM_NEXT; // Read with index_first / index_next
5052
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
5056
/** Update the dependency map for the tables. */
5057
static void update_depend_map(JOIN *join)
5059
JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
5061
for (; join_tab != end ; join_tab++)
5063
table_reference_st *ref= &join_tab->ref;
5064
table_map depend_map= 0;
5065
Item **item=ref->items;
5067
for (i=0 ; i < ref->key_parts ; i++,item++)
5068
depend_map|=(*item)->used_tables();
5069
ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;
5070
depend_map&= ~OUTER_REF_TABLE_BIT;
5071
for (JoinTable **tab=join->map2table; depend_map; tab++,depend_map>>=1 )
5074
ref->depend_map|=(*tab)->ref.depend_map;
5079
/** Update the dependency map for the sort order. */
5080
static void update_depend_map(JOIN *join, order_st *order)
5082
for (; order ; order=order->next)
5084
table_map depend_map;
5085
order->item[0]->update_used_tables();
5086
order->depend_map=depend_map=order->item[0]->used_tables();
5087
// Not item_sum(), RAND() and no reference to table outside of sub select
5088
if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))
5089
&& !order->item[0]->with_sum_func)
5091
for (JoinTable **tab=join->map2table; depend_map; tab++, depend_map>>=1)
5094
order->depend_map|=(*tab)->ref.depend_map;
5101
Remove all constants and check if order_st only contains simple
5104
simple_order is set to 1 if sort_order only uses fields from head table
5105
and the head table is not a LEFT JOIN table.
5107
@param join Join handler
5108
@param first_order List of SORT or GROUP order
5109
@param cond WHERE statement
5110
@param change_list Set to 1 if we should remove things from list.
5111
If this is not set, then only simple_order is
5113
@param simple_order Set to 1 if we are only using simple expressions
5116
Returns new sort order
5118
static order_st *remove_constants(JOIN *join,order_st *first_order, COND *cond, bool change_list, bool *simple_order)
5120
if (join->tables == join->const_tables)
5121
return change_list ? 0 : first_order; // No need to sort
5123
order_st *order,**prev_ptr;
5124
table_map first_table= join->join_tab[join->const_tables].table->map;
5125
table_map not_const_tables= ~join->const_table_map;
5128
prev_ptr= &first_order;
5129
*simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;
5131
/* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
5133
update_depend_map(join, first_order);
5134
for (order=first_order; order ; order=order->next)
5136
table_map order_tables=order->item[0]->used_tables();
5137
if (order->item[0]->with_sum_func)
5138
*simple_order=0; // Must do a temp table to sort
5139
else if (!(order_tables & not_const_tables))
5141
if (order->item[0]->with_subselect)
5142
order->item[0]->val_str(&order->item[0]->str_value);
5143
continue; // skip const item
5147
if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))
5152
if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
5156
if ((ref=order_tables & (not_const_tables ^ first_table)))
5158
if (!(order_tables & first_table) &&
5159
only_eq_ref_tables(join,first_order, ref))
5163
*simple_order=0; // Must do a temp table to sort
5168
*prev_ptr= order; // use this entry
5169
prev_ptr= &order->next;
5173
if (prev_ptr == &first_order) // Nothing to sort/group
5175
return(first_order);
5178
static int return_zero_rows(JOIN *join,
5179
select_result *result,
5183
uint64_t select_options,
5187
if (select_options & SELECT_DESCRIBE)
5189
optimizer::ExplainPlan planner(join,
5194
planner.printPlan();
5202
for (TableList *table= tables; table; table= table->next_leaf)
5203
table->table->mark_as_null_row(); // All fields are NULL
5204
if (having && having->val_int() == 0)
5207
if (! (result->send_fields(fields)))
5211
List_iterator_fast<Item> it(fields);
5213
while ((item= it++))
5214
item->no_rows_in_result();
5215
result->send_data(fields);
5217
result->send_eof(); // Should be safe
5219
/* Update results for FOUND_ROWS */
5220
join->session->limit_found_rows= join->session->examined_row_count= 0;
5225
Simplify joins replacing outer joins by inner joins whenever it's
5228
The function, during a retrieval of join_list, eliminates those
5229
outer joins that can be converted into inner join, possibly nested.
5230
It also moves the on expressions for the converted outer joins
5231
and from inner joins to conds.
5232
The function also calculates some attributes for nested joins:
5236
- on_expr_dep_tables
5237
The first two attributes are used to test whether an outer join can
5238
be substituted for an inner join. The third attribute represents the
5239
relation 'to be dependent on' for tables. If table t2 is dependent
5240
on table t1, then in any evaluated execution plan table access to
5241
table t2 must precede access to table t2. This relation is used also
5242
to check whether the query contains invalid cross-references.
5243
The forth attribute is an auxiliary one and is used to calculate
5245
As the attribute dep_tables qualifies possibles orders of tables in the
5246
execution plan, the dependencies required by the straight join
5247
modifiers are reflected in this attribute as well.
5248
The function also removes all braces that can be removed from the join
5249
expression without changing its meaning.
5252
An outer join can be replaced by an inner join if the where condition
5253
or the on expression for an embedding nested join contains a conjunctive
5254
predicate rejecting null values for some attribute of the inner tables.
5258
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5260
the predicate t2.b < 5 rejects nulls.
5261
The query is converted first to:
5263
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5265
then to the equivalent form:
5267
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
5271
Similarly the following query:
5273
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
5278
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
5282
One conversion might trigger another:
5284
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
5285
LEFT JOIN t3 ON t3.b=t2.b
5286
WHERE t3 IS NOT NULL =>
5287
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
5288
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
5289
SELECT * FROM t1, t2, t3
5290
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
5293
The function removes all unnecessary braces from the expression
5294
produced by the conversions.
5297
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5299
finally is converted to:
5301
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5306
It also will remove braces from the following queries:
5308
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
5309
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
5312
The benefit of this simplification procedure is that it might return
5313
a query for which the optimizer can evaluate execution plan with more
5314
join orders. With a left join operation the optimizer does not
5315
consider any plan where one of the inner tables is before some of outer
5319
The function is implemented by a recursive procedure. On the recursive
5320
ascent all attributes are calculated, all outer joins that can be
5321
converted are replaced and then all unnecessary braces are removed.
5322
As join list contains join tables in the reverse order sequential
5323
elimination of outer joins does not require extra recursive calls.
5326
Remove all semi-joins that have are within another semi-join (i.e. have
5327
an "ancestor" semi-join nest)
5330
Here is an example of a join query with invalid cross references:
5332
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
5335
@param join reference to the query info
5336
@param join_list list representation of the join to be converted
5337
@param conds conditions to add on expressions for converted joins
5338
@param top true <=> conds is the where condition
5341
- The new condition, if success
5344
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top)
5347
nested_join_st *nested_join;
5348
TableList *prev_table= 0;
5349
List_iterator<TableList> li(*join_list);
5352
Try to simplify join operations from join_list.
5353
The most outer join operation is checked for conversion first.
5355
while ((table= li++))
5357
table_map used_tables;
5358
table_map not_null_tables= (table_map) 0;
5360
if ((nested_join= table->nested_join))
5363
If the element of join_list is a nested join apply
5364
the procedure to its nested join list first.
5368
Item *expr= table->on_expr;
5370
If an on expression E is attached to the table,
5371
check all null rejected predicates in this expression.
5372
If such a predicate over an attribute belonging to
5373
an inner table of an embedded outer join is found,
5374
the outer join is converted to an inner join and
5375
the corresponding on expression is added to E.
5377
expr= simplify_joins(join, &nested_join->join_list, expr, false);
5379
if (!table->prep_on_expr || expr != table->on_expr)
5383
table->on_expr= expr;
5384
table->prep_on_expr= expr->copy_andor_structure(join->session);
5387
nested_join->used_tables= (table_map) 0;
5388
nested_join->not_null_tables=(table_map) 0;
5389
conds= simplify_joins(join, &nested_join->join_list, conds, top);
5390
used_tables= nested_join->used_tables;
5391
not_null_tables= nested_join->not_null_tables;
5395
if (!table->prep_on_expr)
5396
table->prep_on_expr= table->on_expr;
5397
used_tables= table->table->map;
5399
not_null_tables= conds->not_null_tables();
5402
if (table->embedding)
5404
table->embedding->nested_join->used_tables|= used_tables;
5405
table->embedding->nested_join->not_null_tables|= not_null_tables;
5408
if (!table->outer_join || (used_tables & not_null_tables))
5411
For some of the inner tables there are conjunctive predicates
5412
that reject nulls => the outer join can be replaced by an inner join.
5414
table->outer_join= 0;
5417
/* Add ON expression to the WHERE or upper-level ON condition. */
5420
conds= and_conds(conds, table->on_expr);
5421
conds->top_level_item();
5422
/* conds is always a new item as both cond and on_expr existed */
5423
assert(!conds->fixed);
5424
conds->fix_fields(join->session, &conds);
5427
conds= table->on_expr;
5428
table->prep_on_expr= table->on_expr= 0;
5436
Only inner tables of non-convertible outer joins
5437
remain with on_expr.
5441
table->dep_tables|= table->on_expr->used_tables();
5442
if (table->embedding)
5444
table->dep_tables&= ~table->embedding->nested_join->used_tables;
5446
Embedding table depends on tables used
5447
in embedded on expressions.
5449
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
5452
table->dep_tables&= ~table->table->map;
5457
/* The order of tables is reverse: prev_table follows table */
5458
if (prev_table->straight)
5459
prev_table->dep_tables|= used_tables;
5460
if (prev_table->on_expr)
5462
prev_table->dep_tables|= table->on_expr_dep_tables;
5463
table_map prev_used_tables= prev_table->nested_join ?
5464
prev_table->nested_join->used_tables :
5465
prev_table->table->map;
5467
If on expression contains only references to inner tables
5468
we still make the inner tables dependent on the outer tables.
5469
It would be enough to set dependency only on one outer table
5470
for them. Yet this is really a rare case.
5472
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5473
prev_table->dep_tables|= used_tables;
5480
Flatten nested joins that can be flattened.
5481
no ON expression and not a semi-join => can be flattened.
5484
while ((table= li++))
5486
nested_join= table->nested_join;
5487
if (nested_join && !table->on_expr)
5490
List_iterator<TableList> it(nested_join->join_list);
5493
tbl->embedding= table->embedding;
5494
tbl->join_list= table->join_list;
5496
li.replace(nested_join->join_list);
5502
static int remove_duplicates(JOIN *join, Table *entry,List<Item> &fields, Item *having)
5505
uint32_t reclength,offset;
5506
uint32_t field_count;
5507
Session *session= join->session;
5509
entry->reginfo.lock_type=TL_WRITE;
5511
/* Calculate how many saved fields there is in list */
5513
List_iterator<Item> it(fields);
5517
if (item->get_tmp_table_field() && ! item->const_item())
5521
if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)
5522
{ // only const items with no OPTION_FOUND_ROWS
5523
join->unit->select_limit_cnt= 1; // Only send first row
5526
Field **first_field=entry->field+entry->s->fields - field_count;
5527
offset= (field_count ?
5528
entry->field[entry->s->fields - field_count]->
5529
offset(entry->record[0]) : 0);
5530
reclength= entry->s->reclength-offset;
5532
entry->free_io_cache(); // Safety
5533
entry->cursor->info(HA_STATUS_VARIABLE);
5534
if (entry->s->db_type() == heap_engine ||
5535
(!entry->s->blob_fields &&
5536
((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->cursor->stats.records <
5537
session->variables.sortbuff_size)))
5538
error= remove_dup_with_hash_index(join->session, entry,
5539
field_count, first_field,
5542
error= remove_dup_with_compare(join->session, entry, first_field, offset,
5545
free_blobs(first_field);
5550
Function to setup clauses without sum functions.
5552
static int setup_without_group(Session *session,
5553
Item **ref_pointer_array,
5557
List<Item> &all_fields,
5561
bool *hidden_group_fields)
5564
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
5566
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5567
res= session->setup_conds(tables, conds);
5569
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
5570
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
5572
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5573
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
5574
group, hidden_group_fields);
5575
session->lex->allow_sum_func= save_allow_sum_func;
5580
Calculate the best possible join and initialize the join structure.
5587
static bool make_join_statistics(JOIN *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5592
uint32_t table_count;
5593
uint32_t const_count;
5595
table_map found_const_table_map;
5596
table_map all_table_map;
5597
table_map found_ref;
5601
Table **table_vector= NULL;
5602
JoinTable *stat= NULL;
5603
JoinTable *stat_end= NULL;
5605
JoinTable **stat_ref= NULL;
5606
optimizer::KeyUse *keyuse= NULL;
5607
optimizer::KeyUse *start_keyuse= NULL;
5608
table_map outer_join= 0;
5609
vector<optimizer::SargableParam> sargables;
5610
JoinTable *stat_vector[MAX_TABLES+1];
5611
optimizer::Position *partial_pos;
5613
table_count= join->tables;
5614
stat= (JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
5615
stat_ref= (JoinTable**) join->session->alloc(sizeof(JoinTable*)*MAX_TABLES);
5616
table_vector= (Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
5617
if (! stat || ! stat_ref || ! table_vector)
5620
join->best_ref=stat_vector;
5622
stat_end=stat+table_count;
5623
found_const_table_map= all_table_map=0;
5628
s++, tables= tables->next_leaf, i++)
5630
TableList *embedding= tables->embedding;
5633
s->const_keys.reset();
5634
s->checked_keys.reset();
5635
s->needed_reg.reset();
5636
table_vector[i]=s->table=table=tables->table;
5637
table->pos_in_table_list= tables;
5638
error= table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5641
table->print_error(error, MYF(0));
5644
table->quick_keys.reset();
5645
table->reginfo.join_tab=s;
5646
table->reginfo.not_exists_optimize=0;
5647
memset(table->const_key_parts, 0,
5648
sizeof(key_part_map)*table->s->keys);
5649
all_table_map|= table->map;
5651
s->info=0; // For describe
5653
s->dependent= tables->dep_tables;
5654
s->key_dependent= 0;
5655
table->quick_condition_rows= table->cursor->stats.records;
5657
s->on_expr_ref= &tables->on_expr;
5658
if (*s->on_expr_ref)
5660
/* s is the only inner table of an outer join */
5661
if (!table->cursor->stats.records && !embedding)
5663
s->dependent= 0; // Ignore LEFT JOIN depend.
5664
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5667
outer_join|= table->map;
5668
s->embedding_map.reset();
5669
for (;embedding; embedding= embedding->embedding)
5670
s->embedding_map|= embedding->nested_join->nj_map;
5673
if (embedding && !(false && ! embedding->embedding))
5675
/* s belongs to a nested join, maybe to several embedded joins */
5676
s->embedding_map.reset();
5679
nested_join_st *nested_join= embedding->nested_join;
5680
s->embedding_map|= nested_join->nj_map;
5681
s->dependent|= embedding->dep_tables;
5682
embedding= embedding->embedding;
5683
outer_join|= nested_join->used_tables;
5688
if ((table->cursor->stats.records <= 1) && !s->dependent &&
5689
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5690
!join->no_const_tables)
5692
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5696
join->outer_join=outer_join;
5698
if (join->outer_join)
5701
Build transitive closure for relation 'to be dependent on'.
5702
This will speed up the plan search for many cases with outer joins,
5703
as well as allow us to catch illegal cross references/
5704
Warshall's algorithm is used to build the transitive closure.
5705
As we use bitmaps to represent the relation the complexity
5706
of the algorithm is O((number of tables)^2).
5708
for (i= 0, s= stat ; i < table_count ; i++, s++)
5710
for (uint32_t j= 0 ; j < table_count ; j++)
5712
table= stat[j].table;
5713
if (s->dependent & table->map)
5714
s->dependent |= table->reginfo.join_tab->dependent;
5717
s->table->maybe_null= 1;
5719
/* Catch illegal cross references for outer joins */
5720
for (i= 0, s= stat ; i < table_count ; i++, s++)
5722
if (s->dependent & s->table->map)
5724
join->tables=0; // Don't use join->table
5725
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
5728
s->key_dependent= s->dependent;
5732
if (conds || outer_join)
5733
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
5734
conds, join->cond_equal,
5735
~outer_join, join->select_lex, sargables))
5738
/* Read tables with 0 or 1 rows (system tables) */
5739
join->const_table_map= 0;
5741
optimizer::Position *p_pos= join->getFirstPosInPartialPlan();
5742
optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5743
while (p_pos < p_end)
5746
s= p_pos->getJoinTable();
5748
join->const_table_map|=s->table->map;
5749
if ((tmp= join_read_const_table(s, p_pos)))
5752
return 1; // Fatal error
5755
found_const_table_map|= s->table->map;
5759
/* loop until no more const tables are found */
5763
more_const_tables_found:
5768
We only have to loop from stat_vector + const_count as
5769
set_position() will move all const_tables first in stat_vector
5772
for (JoinTable **pos= stat_vector+const_count; (s= *pos); pos++)
5777
If equi-join condition by a key is null rejecting and after a
5778
substitution of a const table the key value happens to be null
5779
then we can state that there are no matches for this equi-join.
5781
if ((keyuse= s->keyuse) && *s->on_expr_ref && s->embedding_map.none())
5784
When performing an outer join operation if there are no matching rows
5785
for the single row of the outer table all the inner tables are to be
5786
null complemented and thus considered as constant tables.
5787
Here we apply this consideration to the case of outer join operations
5788
with a single inner table only because the case with nested tables
5789
would require a more thorough analysis.
5790
TODO. Apply single row substitution to null complemented inner tables
5791
for nested outer join operations.
5793
while (keyuse->getTable() == table)
5795
if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&
5796
keyuse->getVal()->is_null() && keyuse->isNullRejected())
5799
table->mark_as_null_row();
5800
found_const_table_map|= table->map;
5801
join->const_table_map|= table->map;
5802
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5803
goto more_const_tables_found;
5809
if (s->dependent) // If dependent on some table
5811
// All dep. must be constants
5812
if (s->dependent & ~(found_const_table_map))
5814
if (table->cursor->stats.records <= 1L &&
5815
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5816
!table->pos_in_table_list->embedding)
5820
join->const_table_map|=table->map;
5821
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5822
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5823
if ((tmp= join_read_const_table(s, partial_pos)))
5826
return 1; // Fatal error
5829
found_const_table_map|= table->map;
5833
/* check if table can be read by key or table only uses const refs */
5834
if ((keyuse=s->keyuse))
5837
while (keyuse->getTable() == table)
5839
start_keyuse= keyuse;
5840
key= keyuse->getKey();
5841
s->keys.set(key); // QQ: remove this ?
5848
if (keyuse->getVal()->type() != Item::NULL_ITEM &&
5849
! keyuse->getOptimizeFlags())
5851
if (! ((~found_const_table_map) & keyuse->getUsedTables()))
5852
const_ref.set(keyuse->getKeypart());
5854
refs|= keyuse->getUsedTables();
5855
eq_part.set(keyuse->getKeypart());
5858
} while (keyuse->getTable() == table && keyuse->getKey() == key);
5860
if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
5861
! table->pos_in_table_list->embedding)
5863
if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
5865
if (const_ref == eq_part)
5866
{ // Found everything for ref.
5870
join->const_table_map|= table->map;
5871
set_position(join, const_count++, s, start_keyuse);
5872
if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
5874
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5875
if ((tmp=join_read_const_table(s, partial_pos)))
5878
return 1; // Fatal error
5881
found_const_table_map|= table->map;
5885
found_ref|= refs; // Table is const if all refs are const
5887
else if (const_ref == eq_part)
5888
s->const_keys.set(key);
5893
} while (join->const_table_map & found_ref && ref_changed);
5896
Update info on indexes that can be used for search lookups as
5897
reading const tables may has added new sargable predicates.
5899
if (const_count && ! sargables.empty())
5901
vector<optimizer::SargableParam>::iterator iter= sargables.begin();
5902
while (iter != sargables.end())
5904
Field *field= (*iter).getField();
5905
JoinTable *join_tab= field->table->reginfo.join_tab;
5906
key_map possible_keys= field->key_start;
5907
possible_keys&= field->table->keys_in_use_for_query;
5908
bool is_const= true;
5909
for (uint32_t j= 0; j < (*iter).getNumValues(); j++)
5910
is_const&= (*iter).isConstItem(j);
5912
join_tab[0].const_keys|= possible_keys;
5917
/* Calc how many (possible) matched records in each table */
5919
for (s=stat ; s < stat_end ; s++)
5921
if (s->type == AM_SYSTEM || s->type == AM_CONST)
5923
/* Only one matching row */
5924
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
5927
/* Approximate found rows and time to read them */
5928
s->found_records=s->records=s->table->cursor->stats.records;
5929
s->read_time=(ha_rows) s->table->cursor->scan_time();
5932
Set a max range of how many seeks we can expect when using keys
5933
This is can't be to high as otherwise we are likely to use
5936
s->worst_seeks= min((double) s->found_records / 10,
5937
(double) s->read_time*3);
5938
if (s->worst_seeks < 2.0) // Fix for small tables
5942
Add to stat->const_keys those indexes for which all group fields or
5943
all select distinct fields participate in one index.
5945
add_group_and_distinct_keys(join, s);
5947
if (s->const_keys.any() &&
5948
!s->table->pos_in_table_list->embedding)
5951
optimizer::SqlSelect *select= NULL;
5952
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);
5955
records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
5956
s->quick=select->quick;
5957
s->needed_reg=select->needed_reg;
5959
if (records == 0 && s->table->reginfo.impossible_range)
5962
Impossible WHERE or ON expression
5963
In case of ON, we mark that the we match one empty NULL row.
5964
In case of WHERE, don't set found_const_table_map to get the
5965
caller to abort with a zero row result.
5967
join->const_table_map|= s->table->map;
5968
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5970
if (*s->on_expr_ref)
5972
/* Generate empty row */
5973
s->info= "Impossible ON condition";
5974
found_const_table_map|= s->table->map;
5976
s->table->mark_as_null_row(); // All fields are NULL
5979
if (records != HA_POS_ERROR)
5981
s->found_records=records;
5982
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
5988
join->join_tab=stat;
5989
join->map2table=stat_ref;
5990
join->table= join->all_tables=table_vector;
5991
join->const_tables=const_count;
5992
join->found_const_table_map=found_const_table_map;
5994
/* Find an optimal join order of the non-constant tables. */
5995
if (join->const_tables != join->tables)
5997
optimize_keyuse(join, keyuse_array);
5998
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->query, join->session->thread_id);
5999
bool res= choose_plan(join, all_table_map & ~join->const_table_map);
6000
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);
6006
join->copyPartialPlanIntoOptimalPlan(join->const_tables);
6007
join->best_read= 1.0;
6009
/* Generate an execution plan from the found optimal join order. */
6010
return (join->session->killed || get_best_combination(join));
6014
Assign each nested join structure a bit in the nested join bitset.
6016
Assign each nested join structure (except "confluent" ones - those that
6017
embed only one element) a bit in the nested join bitset.
6019
@param join Join being processed
6020
@param join_list List of tables
6021
@param first_unused Number of first unused bit in the nest joing bitset before the
6025
This function is called after simplify_joins(), when there are no
6026
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
6027
we will not run out of bits in the nested join bitset.
6030
First unused bit in the nest join bitset after the call.
6032
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
6034
List_iterator<TableList> li(*join_list);
6036
while ((table= li++))
6038
nested_join_st *nested_join;
6039
if ((nested_join= table->nested_join))
6042
It is guaranteed by simplify_joins() function that a nested join
6043
that has only one child is either
6044
- a single-table view (the child is the underlying table), or
6045
- a single-table semi-join nest
6047
We don't assign bits to such sj-nests because
6048
1. it is redundant (a "sequence" of one table cannot be interleaved
6050
2. we could run out of bits in the nested join bitset otherwise.
6052
if (nested_join->join_list.elements != 1)
6054
/* Don't assign bits to sj-nests */
6056
nested_join->nj_map.set(first_unused++);
6057
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
6062
return(first_unused);
6067
Return table number if there is only one table in sort order
6068
and group and order is compatible, else return 0.
6070
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables)
6072
table_map map= (table_map) 0;
6075
a= b; // Only one need to be given
6079
for (; a && b; a=a->next,b=b->next)
6081
if (!(*a->item)->eq(*b->item,1))
6082
return (Table *) NULL;
6083
map|= a->item[0]->used_tables();
6085
if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
6086
return (Table *) NULL;
6088
for (; !(map & tables->table->map); tables= tables->next_leaf) {};
6089
if (map != tables->table->map)
6090
return (Table *) NULL; // More than one table
6091
return tables->table;
6095
Set nested_join_st::counter=0 in all nested joins in passed list.
6097
Recursively set nested_join_st::counter=0 for all nested joins contained in
6098
the passed join_list.
6100
@param join_list List of nested joins to process. It may also contain base
6101
tables which will be ignored.
6103
static void reset_nj_counters(List<TableList> *join_list)
6105
List_iterator<TableList> li(*join_list);
6107
while ((table= li++))
6109
nested_join_st *nested_join;
6110
if ((nested_join= table->nested_join))
6112
nested_join->counter_= 0;
6113
reset_nj_counters(&nested_join->join_list);
6120
Return 1 if second is a subpart of first argument.
6122
If first parts has different direction, change it to second part
6123
(group is sorted like order)
6125
static bool test_if_subpart(order_st *a,order_st *b)
6127
for (; a && b; a=a->next,b=b->next)
6129
if ((*a->item)->eq(*b->item,1))
6138
Nested joins perspective: Remove the last table from the join order.
6140
Remove the last table from the partial join order and update the nested
6141
joins counters and join->cur_embedding_map. It is ok to call this
6142
function for the first table in join order (for which
6143
check_interleaving_with_nj has not been called)
6145
@param last join table to remove, it is assumed to be the last in current
6148
static void restore_prev_nj_state(JoinTable *last)
6150
TableList *last_emb= last->table->pos_in_table_list->embedding;
6151
JOIN *join= last->join;
6154
if (last_emb->on_expr)
6156
if (!(--last_emb->nested_join->counter_))
6157
join->cur_embedding_map&= ~last_emb->nested_join->nj_map;
6158
else if (last_emb->nested_join->join_list.elements-1 ==
6159
last_emb->nested_join->counter_)
6160
join->cur_embedding_map|= last_emb->nested_join->nj_map;
6164
last_emb= last_emb->embedding;
6169
Determine if the set is already ordered for order_st BY, so it can
6170
disable join cache because it will change the ordering of the results.
6171
Code handles sort table that is at any location (not only first after
6172
the const tables) despite the fact that it's currently prohibited.
6173
We must disable join cache if the first non-const table alone is
6174
ordered. If there is a temp table the ordering is done as a last
6175
operation and doesn't prevent join cache usage.
6177
static uint32_t make_join_orderinfo(JOIN *join)
6181
return join->tables;
6183
for (i=join->const_tables ; i < join->tables ; i++)
6185
JoinTable *tab= join->join_tab+i;
6186
Table *table= tab->table;
6187
if ((table == join->sort_by_table &&
6188
(!join->order || join->skip_sort_order)) ||
6189
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
6198
Create a condition for a const reference and add this to the
6199
currenct select for the table.
6201
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)
6203
if (!join_tab->ref.key_parts)
6206
Item_cond_and *cond=new Item_cond_and();
6207
Table *table=join_tab->table;
6212
for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6214
Field *field=table->field[table->key_info[join_tab->ref.key].key_part[i].
6216
Item *value=join_tab->ref.items[i];
6217
cond->add(new Item_func_equal(new Item_field(field), value));
6219
if (session->is_fatal_error)
6223
cond->fix_fields(session, (Item**)&cond);
6224
if (join_tab->select)
6226
error=(int) cond->add(join_tab->select->cond);
6227
join_tab->select_cond=join_tab->select->cond=cond;
6229
else if ((join_tab->select= optimizer::make_select(join_tab->table, 0, 0, cond, 0,
6231
join_tab->select_cond=cond;
6233
return(error ? true : false);
6236
static void free_blobs(Field **ptr)
6238
for (; *ptr ; ptr++)
6240
if ((*ptr)->flags & BLOB_FLAG)
6241
((Field_blob *) (*ptr))->free();
6246
@} (end of group Query_Optimizer)
6249
} /* namespace drizzled */
added
removed
drizzled/join.cc
