20
20
mysql_select and join optimization
22
23
@defgroup Query_Optimizer Query Optimizer
25
#include "drizzled/server_includes.h"
32
#include "drizzled/sql_select.h" /* include join.h */
33
#include "drizzled/table_map_iterator.h"
35
#include "drizzled/error.h"
36
#include "drizzled/gettext.h"
37
#include "drizzled/util/test.h"
38
#include "drizzled/name_resolution_context_state.h"
39
#include "drizzled/nested_join.h"
40
#include "drizzled/probes.h"
41
#include "drizzled/show.h"
42
#include "drizzled/plugin/info_schema_table.h"
43
#include "drizzled/item/cache.h"
44
#include "drizzled/item/cmpfunc.h"
45
#include "drizzled/item/copy_string.h"
46
#include "drizzled/item/uint.h"
47
#include "drizzled/cached_item.h"
48
#include "drizzled/sql_base.h"
49
#include "drizzled/field/blob.h"
50
#include "drizzled/check_stack_overrun.h"
51
#include "drizzled/lock.h"
52
#include "drizzled/item/outer_ref.h"
53
#include "drizzled/index_hint.h"
54
#include "drizzled/memory/multi_malloc.h"
56
#include "drizzled/sql_union.h"
57
#include "drizzled/optimizer/key_field.h"
58
#include "drizzled/optimizer/position.h"
59
#include "drizzled/optimizer/sargable_param.h"
60
#include "drizzled/optimizer/key_use.h"
63
using namespace drizzled;
65
static const string access_method_str[]=
26
#include <drizzled/server_includes.h>
27
#include <drizzled/sql_select.h>
28
#include "sj_tmp_table.h"
30
#include <mysys/my_bit.h>
31
#include <drizzled/drizzled_error_messages.h>
33
const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
34
"MAYBE_REF","ALL","range","index",
35
"ref_or_null","unique_subquery","index_subquery",
82
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);
83
static COND *build_equal_items(Session *session, COND *cond,
39
struct st_sargable_param;
41
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
42
static bool make_join_statistics(JOIN *join, TABLE_LIST *leaves, COND *conds,
43
DYNAMIC_ARRAY *keyuse);
44
static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,
46
uint tables, COND *conds,
47
COND_EQUAL *cond_equal,
48
table_map table_map, SELECT_LEX *select_lex,
49
st_sargable_param **sargables);
50
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
51
static void set_position(JOIN *join,uint index,JOIN_TAB *table,KEYUSE *key);
52
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
53
table_map used_tables);
54
static bool choose_plan(JOIN *join,table_map join_tables);
56
static void best_access_path(JOIN *join, JOIN_TAB *s, THD *thd,
57
table_map remaining_tables, uint idx,
58
double record_count, double read_time);
59
static void optimize_straight_join(JOIN *join, table_map join_tables);
60
static bool greedy_search(JOIN *join, table_map remaining_tables,
61
uint depth, uint prune_level);
62
static bool best_extension_by_limited_search(JOIN *join,
63
table_map remaining_tables,
64
uint idx, double record_count,
65
double read_time, uint depth,
67
static uint determine_search_depth(JOIN* join);
68
static int join_tab_cmp(const void* ptr1, const void* ptr2);
69
static int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
71
TODO: 'find_best' is here only temporarily until 'greedy_search' is
74
static bool find_best(JOIN *join,table_map rest_tables,uint index,
75
double record_count,double read_time);
76
static uint cache_record_length(JOIN *join,uint index);
77
static double prev_record_reads(JOIN *join, uint idx, table_map found_ref);
78
static bool get_best_combination(JOIN *join);
79
static store_key *get_store_key(THD *thd,
80
KEYUSE *keyuse, table_map used_tables,
81
KEY_PART_INFO *key_part, uchar *key_buff,
83
static bool make_simple_join(JOIN *join,TABLE *tmp_table);
84
static void make_outerjoin_info(JOIN *join);
85
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
86
static bool make_join_readinfo(JOIN *join, uint64_t options, uint no_jbuf_after);
87
static bool only_eq_ref_tables(JOIN *join, ORDER *order, table_map tables);
88
static void update_depend_map(JOIN *join);
89
static void update_depend_map(JOIN *join, ORDER *order);
90
static ORDER *remove_const(JOIN *join,ORDER *first_order,COND *cond,
91
bool change_list, bool *simple_order);
92
static int return_zero_rows(JOIN *join, select_result *res,TABLE_LIST *tables,
93
List<Item> &fields, bool send_row,
94
uint64_t select_options, const char *info,
96
static COND *build_equal_items(THD *thd, COND *cond,
84
97
COND_EQUAL *inherited,
85
List<TableList> *join_list,
98
List<TABLE_LIST> *join_list,
86
99
COND_EQUAL **cond_equal_ref);
88
static Item* part_of_refkey(Table *form,Field *field);
89
static bool cmp_buffer_with_ref(JoinTable *tab);
90
static void change_cond_ref_to_const(Session *session,
91
vector<COND_CMP>& save_list,
96
static bool copy_blobs(Field **ptr);
98
static bool eval_const_cond(COND *cond)
100
return ((Item_func*) cond)->val_int() ? true : false;
100
static COND* substitute_for_best_equal_field(COND *cond,
101
COND_EQUAL *cond_equal,
102
void *table_join_idx);
103
static COND *simplify_joins(JOIN *join, List<TABLE_LIST> *join_list,
104
COND *conds, bool top, bool in_sj);
105
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
106
static void restore_prev_nj_state(JOIN_TAB *last);
107
static void reset_nj_counters(List<TABLE_LIST> *join_list);
108
static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list,
112
void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);
113
static void restore_prev_sj_state(const table_map remaining_tables,
114
const JOIN_TAB *tab);
116
static COND *optimize_cond(JOIN *join, COND *conds,
117
List<TABLE_LIST> *join_list,
118
Item::cond_result *cond_value);
119
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
120
static int do_select(JOIN *join,List<Item> *fields,TABLE *tmp_table);
122
static enum_nested_loop_state
123
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
125
static enum_nested_loop_state
126
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
127
static enum_nested_loop_state
128
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
129
static enum_nested_loop_state
130
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
131
static enum_nested_loop_state
132
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
133
static enum_nested_loop_state
134
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
135
static enum_nested_loop_state
136
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
138
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
139
static int join_read_system(JOIN_TAB *tab);
140
static int join_read_const(JOIN_TAB *tab);
141
static int join_read_key(JOIN_TAB *tab);
142
static int join_read_always_key(JOIN_TAB *tab);
143
static int join_read_last_key(JOIN_TAB *tab);
144
static int join_no_more_records(READ_RECORD *info);
145
static int join_read_next(READ_RECORD *info);
146
static int join_read_next_different(READ_RECORD *info);
147
static int join_init_quick_read_record(JOIN_TAB *tab);
148
static int test_if_quick_select(JOIN_TAB *tab);
149
static int join_init_read_record(JOIN_TAB *tab);
150
static int join_read_first(JOIN_TAB *tab);
151
static int join_read_next_same(READ_RECORD *info);
152
static int join_read_next_same_diff(READ_RECORD *info);
153
static int join_read_last(JOIN_TAB *tab);
154
static int join_read_prev_same(READ_RECORD *info);
155
static int join_read_prev(READ_RECORD *info);
156
int join_read_always_key_or_null(JOIN_TAB *tab);
157
int join_read_next_same_or_null(READ_RECORD *info);
158
static COND *make_cond_for_table(COND *cond,table_map table,
159
table_map used_table,
160
bool exclude_expensive_cond);
161
static Item* part_of_refkey(TABLE *form,Field *field);
162
static bool test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,
163
ha_rows select_limit, bool no_changes,
165
static bool list_contains_unique_index(TABLE *table,
166
bool (*find_func) (Field *, void *), void *data);
167
static bool find_field_in_item_list (Field *field, void *data);
168
static bool find_field_in_order_list (Field *field, void *data);
169
static int create_sort_index(THD *thd, JOIN *join, ORDER *order,
170
ha_rows filesort_limit, ha_rows select_limit,
172
static int remove_duplicates(JOIN *join,TABLE *entry,List<Item> &fields,
174
static int remove_dup_with_compare(THD *thd, TABLE *entry, Field **field,
175
ulong offset,Item *having);
176
static int remove_dup_with_hash_index(THD *thd,TABLE *table,
177
uint field_count, Field **first_field,
179
ulong key_length,Item *having);
180
static int join_init_cache(THD *thd,JOIN_TAB *tables,uint table_count);
181
static ulong used_blob_length(CACHE_FIELD **ptr);
182
static bool store_record_in_cache(JOIN_CACHE *cache);
183
static void reset_cache_read(JOIN_CACHE *cache);
184
static void reset_cache_write(JOIN_CACHE *cache);
185
static void read_cached_record(JOIN_TAB *tab);
186
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
187
static ORDER *create_distinct_group(THD *thd, Item **ref_pointer_array,
188
ORDER *order, List<Item> &fields,
189
List<Item> &all_fields,
190
bool *all_order_by_fields_used);
191
static bool test_if_subpart(ORDER *a,ORDER *b);
192
static TABLE *get_sort_by_table(ORDER *a,ORDER *b,TABLE_LIST *tables);
193
static void calc_group_buffer(JOIN *join,ORDER *group);
194
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
195
static bool alloc_group_fields(JOIN *join,ORDER *group);
196
// Create list for using with tempory table
197
static bool change_to_use_tmp_fields(THD *thd, Item **ref_pointer_array,
198
List<Item> &new_list1,
199
List<Item> &new_list2,
200
uint elements, List<Item> &items);
201
// Create list for using with tempory table
202
static bool change_refs_to_tmp_fields(THD *thd, Item **ref_pointer_array,
203
List<Item> &new_list1,
204
List<Item> &new_list2,
205
uint elements, List<Item> &items);
206
static void init_tmptable_sum_functions(Item_sum **func);
207
static void update_tmptable_sum_func(Item_sum **func,TABLE *tmp_table);
208
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
209
static bool add_ref_to_table_cond(THD *thd, JOIN_TAB *join_tab);
210
static bool setup_sum_funcs(THD *thd, Item_sum **func_ptr);
211
static bool init_sum_functions(Item_sum **func, Item_sum **end);
212
static bool update_sum_func(Item_sum **func);
213
void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
214
bool distinct, const char *message=NullS);
215
static Item *remove_additional_cond(Item* conds);
216
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
217
static bool test_if_ref(Item_field *left_item,Item *right_item);
218
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
219
Item *new_cond, bool fix_fields);
104
222
This is used to mark equalities that were made from i-th IN-equality.
267
381
ref->outer_ref= new_ref;
268
382
ref->ref= &ref->outer_ref;
270
if (!ref->fixed && ref->fix_fields(session, 0))
384
if (!ref->fixed && ref->fix_fields(thd, 0))
272
session->used_tables|= item->used_tables();
386
thd->used_tables|= item->used_tables();
391
#define MAGIC_IN_WHERE_TOP_LEVEL 10
393
Function to setup clauses without sum functions.
395
inline int setup_without_group(THD *thd, Item **ref_pointer_array,
399
List<Item> &all_fields,
402
ORDER *group, bool *hidden_group_fields)
405
nesting_map save_allow_sum_func=thd->lex->allow_sum_func ;
407
thd->lex->allow_sum_func&= ~(1 << thd->lex->current_select->nest_level);
408
res= setup_conds(thd, tables, leaves, conds);
410
thd->lex->allow_sum_func|= 1 << thd->lex->current_select->nest_level;
411
res= res || setup_order(thd, ref_pointer_array, tables, fields, all_fields,
413
thd->lex->allow_sum_func&= ~(1 << thd->lex->current_select->nest_level);
414
res= res || setup_group(thd, ref_pointer_array, tables, fields, all_fields,
415
group, hidden_group_fields);
416
thd->lex->allow_sum_func= save_allow_sum_func;
277
420
/*****************************************************************************
278
421
Check fields, find best join, do the select and output fields.
279
422
mysql_select assumes that all tables are already opened
280
423
*****************************************************************************/
426
Prepare of whole select (including sub queries in future).
429
Add check of calculation of GROUP functions and fields:
430
SELECT COUNT(*)+table.col1 from table1;
438
JOIN::prepare(Item ***rref_pointer_array,
439
TABLE_LIST *tables_init,
440
uint wild_num, COND *conds_init, uint og_num,
441
ORDER *order_init, ORDER *group_init,
443
ORDER *proc_param_init, SELECT_LEX *select_lex_arg,
444
SELECT_LEX_UNIT *unit_arg)
446
// to prevent double initialization on EXPLAIN
452
group_list= group_init;
454
proc_param= proc_param_init;
455
tables_list= tables_init;
456
select_lex= select_lex_arg;
457
select_lex->join= this;
458
join_list= &select_lex->top_join_list;
459
union_part= unit_arg->is_union();
461
thd->lex->current_select->is_item_list_lookup= 1;
463
If we have already executed SELECT, then it have not sense to prevent
464
its table from update (see unique_table())
466
if (thd->derived_tables_processing)
467
select_lex->exclude_from_table_unique_test= true;
469
/* Check that all tables, fields, conds and order are ok */
471
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
472
setup_tables_and_check_access(thd, &select_lex->context, join_list,
473
tables_list, &select_lex->leaf_tables,
477
TABLE_LIST *table_ptr;
478
for (table_ptr= select_lex->leaf_tables;
480
table_ptr= table_ptr->next_leaf)
483
if (setup_wild(thd, tables_list, fields_list, &all_fields, wild_num) ||
484
select_lex->setup_ref_array(thd, og_num) ||
485
setup_fields(thd, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
487
setup_without_group(thd, (*rref_pointer_array), tables_list,
488
select_lex->leaf_tables, fields_list,
489
all_fields, &conds, order, group_list,
490
&hidden_group_fields))
491
return(-1); /* purecov: inspected */
493
ref_pointer_array= *rref_pointer_array;
497
nesting_map save_allow_sum_func= thd->lex->allow_sum_func;
498
thd->where="having clause";
499
thd->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
500
select_lex->having_fix_field= 1;
501
bool having_fix_rc= (!having->fixed &&
502
(having->fix_fields(thd, &having) ||
503
having->check_cols(1)));
504
select_lex->having_fix_field= 0;
505
if (having_fix_rc || thd->is_error())
506
return(-1); /* purecov: inspected */
507
thd->lex->allow_sum_func= save_allow_sum_func;
511
Item_subselect *subselect;
512
Item_in_subselect *in_subs= NULL;
514
Are we in a subquery predicate?
515
TODO: the block below will be executed for every PS execution without need.
517
if ((subselect= select_lex->master_unit()->item))
519
bool do_semijoin= !test(thd->variables.optimizer_switch &
520
OPTIMIZER_SWITCH_NO_SEMIJOIN);
521
if (subselect->substype() == Item_subselect::IN_SUBS)
522
in_subs= (Item_in_subselect*)subselect;
525
Check if we're in subquery that is a candidate for flattening into a
526
semi-join (which is done done in flatten_subqueries()). The
528
1. Subquery predicate is an IN/=ANY subq predicate
529
2. Subquery is a single SELECT (not a UNION)
530
3. Subquery does not have GROUP BY or ORDER BY
531
4. Subquery does not use aggregate functions or HAVING
532
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
533
6. No execution method was already chosen (by a prepared statement).
535
(*). We are not in a subquery of a single table UPDATE/DELETE that
536
doesn't have a JOIN (TODO: We should handle this at some
537
point by switching to multi-table UPDATE/DELETE)
539
(**). We're not in a confluent table-less subquery, like
543
!select_lex->master_unit()->first_select()->next_select() && // 2
544
!select_lex->group_list.elements && !order && // 3
545
!having && !select_lex->with_sum_func && // 4
546
thd->thd_marker && // 5
547
select_lex->outer_select()->join && // (*)
548
select_lex->master_unit()->first_select()->leaf_tables && // (**)
550
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
553
if (!in_subs->left_expr->fixed &&
554
in_subs->left_expr->fix_fields(thd, &in_subs->left_expr))
559
Check that the right part of the subselect contains no more than one
560
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
562
if (subselect->substype() == Item_subselect::IN_SUBS &&
563
(select_lex->item_list.elements !=
564
((Item_in_subselect*)subselect)->left_expr->cols()))
566
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
571
/* Register the subquery for further processing */
572
select_lex->outer_select()->join->sj_subselects.append(thd->mem_root, in_subs);
573
in_subs->expr_join_nest= (TABLE_LIST*)thd->thd_marker;
577
bool do_materialize= !test(thd->variables.optimizer_switch &
578
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
580
Check if the subquery predicate can be executed via materialization.
581
The required conditions are:
582
1. Subquery predicate is an IN/=ANY subq predicate
583
2. Subquery is a single SELECT (not a UNION)
584
3. Subquery is not a table-less query. In this case there is no
585
point in materializing.
586
4. Subquery predicate is a top-level predicate
587
(this implies it is not negated)
588
TODO: this is a limitation that should be lifeted once we
589
implement correct NULL semantics (WL#3830)
590
5. Subquery is non-correlated
592
This is an overly restrictive condition. It can be extended to:
593
(Subquery is non-correlated ||
594
Subquery is correlated to any query outer to IN predicate ||
595
(Subquery is correlated to the immediate outer query &&
596
Subquery !contains {GROUP BY, ORDER BY [LIMIT],
597
aggregate functions) && subquery predicate is not under "NOT IN"))
598
6. No execution method was already chosen (by a prepared statement).
600
(*) The subquery must be part of a SELECT statement. The current
601
condition also excludes multi-table update statements.
603
We have to determine whether we will perform subquery materialization
604
before calling the IN=>EXISTS transformation, so that we know whether to
605
perform the whole transformation or only that part of it which wraps
606
Item_in_subselect in an Item_in_optimizer.
608
if (do_materialize &&
610
!select_lex->master_unit()->first_select()->next_select() && // 2
611
select_lex->master_unit()->first_select()->leaf_tables && // 3
612
thd->lex->sql_command == SQLCOM_SELECT) // *
614
if (in_subs->is_top_level_item() && // 4
615
!in_subs->is_correlated && // 5
616
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
617
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
620
Item_subselect::trans_res trans_res;
621
if ((trans_res= subselect->select_transformer(this)) !=
622
Item_subselect::RES_OK)
624
return((trans_res == Item_subselect::RES_ERROR));
633
for (ord= order; ord; ord= ord->next)
635
Item *item= *ord->item;
636
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
637
item->split_sum_func(thd, ref_pointer_array, all_fields);
641
if (having && having->with_sum_func)
642
having->split_sum_func2(thd, ref_pointer_array, all_fields,
644
if (select_lex->inner_sum_func_list)
646
Item_sum *end=select_lex->inner_sum_func_list;
647
Item_sum *item_sum= end;
650
item_sum= item_sum->next;
651
item_sum->split_sum_func2(thd, ref_pointer_array,
652
all_fields, item_sum->ref_by, false);
653
} while (item_sum != end);
656
if (select_lex->inner_refs_list.elements &&
657
fix_inner_refs(thd, all_fields, select_lex, ref_pointer_array))
661
Check if there are references to un-aggregated columns when computing
662
aggregate functions with implicit grouping (there is no GROUP BY).
664
MODE_ONLY_FULL_GROUP_BY is enabled here by default
666
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
668
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
669
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
673
/* Caclulate the number of groups */
675
for (ORDER *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
680
goto err; /* purecov: inspected */
682
if (result && result->prepare(fields_list, unit_arg))
683
goto err; /* purecov: inspected */
685
/* Init join struct */
686
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
687
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
688
this->group= group_list != 0;
691
#ifdef RESTRICTED_GROUP
692
if (sum_func_count && !group_list && (func_count || field_count))
694
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
698
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
700
if (alloc_func_list())
706
return(-1); /* purecov: inspected */
711
Remove the predicates pushed down into the subquery
714
JOIN::remove_subq_pushed_predicates()
715
where IN Must be NULL
716
OUT The remaining WHERE condition, or NULL
719
Given that this join will be executed using (unique|index)_subquery,
720
without "checking NULL", remove the predicates that were pushed down
723
If the subquery compares scalar values, we can remove the condition that
724
was wrapped into trig_cond (it will be checked when needed by the subquery
727
If the subquery compares row values, we need to keep the wrapped
728
equalities in the WHERE clause: when the left (outer) tuple has both NULL
729
and non-NULL values, we'll do a full table scan and will rely on the
730
equalities corresponding to non-NULL parts of left tuple to filter out
731
non-matching records.
733
TODO: We can remove the equalities that will be guaranteed to be true by the
734
fact that subquery engine will be using index lookup. This must be done only
735
for cases where there are no conversion errors of significance, e.g. 257
736
that is searched in a byte. But this requires homogenization of the return
737
codes of all Field*::store() methods.
740
void JOIN::remove_subq_pushed_predicates(Item **where)
742
if (conds->type() == Item::FUNC_ITEM &&
743
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
744
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
745
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
746
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
747
((Item_func *)conds)->arguments()[0]))
283
756
Index lookup-based subquery: save some flags for EXPLAIN output
795
Check if the table's rowid is included in the temptable
798
sj_table_is_included()
800
join_tab The table to be checked
803
SemiJoinDuplicateElimination: check the table's rowid should be included
804
in the temptable. This is so if
806
1. The table is not embedded within some semi-join nest
807
2. The has been pulled out of a semi-join nest, or
809
3. The table is functionally dependent on some previous table
811
[4. This is also true for constant tables that can't be
812
NULL-complemented but this function is not called for such tables]
815
true - Include table's rowid
819
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
821
if (join_tab->emb_sj_nest)
824
/* Check if this table is functionally dependent on the tables that
825
are within the same outer join nest
827
TABLE_LIST *embedding= join_tab->table->pos_in_table_list->embedding;
828
if (join_tab->type == JT_EQ_REF)
830
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
832
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
834
JOIN_TAB *ref_tab= join->join_tab + idx;
835
if (embedding == ref_tab->table->pos_in_table_list->embedding)
838
/* Ok, functionally dependent */
841
/* Not functionally dependent => need to include*/
847
Setup the strategies to eliminate semi-join duplicates.
850
setup_semijoin_dups_elimination()
852
options Join options (needed to see if join buffering will be
854
no_jbuf_after Another bit of information re where join buffering will
858
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
861
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
863
2. FirstMatch (pick only the 1st matching row combination of inner tables)
864
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
865
together and picking the 1st one)
867
The join order has "duplicate-generating ranges", and every range is
868
served by one strategy or a combination of FirstMatch with with some
871
"Duplicate-generating range" is defined as a range within the join order
872
that contains all of the inner tables of a semi-join. All ranges must be
873
disjoint, if tables of several semi-joins are interleaved, then the ranges
874
are joined together, which is equivalent to converting
875
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
877
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
880
Applicability conditions are as follows:
882
DuplicateWeedout strategy
883
~~~~~~~~~~~~~~~~~~~~~~~~~
885
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
886
+------+ +=========================+ +---+
889
(1) - Prefix of OuterTables (those that participate in
890
IN-equality and/or are correlated with subquery) and outer
891
Noncorrelated Tables.
892
(2) - The handled range. The range starts with the first sj-inner
893
table, and covers all sj-inner and outer tables
894
Within the range, Inner, Outer, outer Noncorrelated tables
895
may follow in any order.
896
(3) - The suffix of outer Noncorrelated tables.
901
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
902
+------+ +==================+ +---+
905
(1) - Prefix of outer and non-correlated tables
906
(2) - The handled range, which may contain only inner and
907
non-correlated tables.
908
(3) - The suffix of outer Noncorrelated tables.
913
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
914
+--------+ +===========+ +=============+ +------+
917
(1) - Prefix that may contain any outer tables. The prefix must contain
918
all the non-trivially correlated outer tables. (non-trivially means
919
that the correlation is not just through the IN-equality).
921
(2) - Inner table for which the InsideOut scan is performed.
923
(3) - The remainder of the duplicate-generating range. It is served by
924
application of FirstMatch strategy, with the exception that
925
outer IN-correlated tables are considered to be non-correlated.
927
(4) - THe suffix of outer and outer non-correlated tables.
929
If several strategies are applicable, their relative priorities are:
934
This function walks over the join order and sets up the strategies by
935
setting appropriate members in join_tab structures.
939
true Out of memory error
943
int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint no_jbuf_after)
945
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
948
0 - invalid (EOF marker),
950
2 - Temptable (maybe confluent),
951
3 - Temptable with join buffering
954
uint start_idx; /* Left range bound */
955
uint end_idx; /* Right range bound */
957
For Temptable strategy: Bitmap of all outer and correlated tables from
958
all involved join nests.
960
table_map outer_tables;
961
} dups_ranges [MAX_TABLES];
963
TABLE_LIST *emb_insideout_nest= NULL;
964
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
965
tables) whose ranges we're in */
966
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
967
table_map range_start_map= 0; /* table_map at current range start */
968
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
973
First pass: locate the duplicate-generating ranges and pick the strategies.
975
for (i=join->const_tables ; i < join->tables ; i++)
977
JOIN_TAB *tab=join->join_tab+i;
978
TABLE *table=tab->table;
979
cur_map |= table->map;
981
if (tab->emb_sj_nest) // Encountered an sj-inner table
985
dups_ranges[cur_range].start_idx= i;
986
range_start_map= cur_map & ~table->map;
988
Remember if this is a possible start of range that is covered by
989
the InsideOut strategy (the reason that it is not covered could
990
be that it overlaps with anther semi-join's range. we don't
991
support InsideOut for joined ranges)
993
if (join->best_positions[i].use_insideout_scan)
994
emb_insideout_nest= tab->emb_sj_nest;
997
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
998
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
1000
if (tab->emb_sj_nest != emb_insideout_nest)
1003
Two different semi-joins interleave. This cannot be handled by
1006
emb_insideout_nest= NULL;
1010
if (emb_sj_map) /* We're in duplicate-generating range */
1012
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
1013
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
1014
i <= no_jbuf_after && !dealing_with_jbuf)
1017
This table uses join buffering, which makes use of FirstMatch or
1018
InsideOut strategies impossible for the current and (we assume)
1019
preceding duplicate-producing ranges.
1020
That is, for the join order:
1022
x x [ x x] x [x x x] x [x x X* x] x
1024
+-----+ +-----+ | join buffering use
1027
we'll have to remove r1 and r2 and use duplicate-elimination
1028
strategy that spans all the tables, starting from the very 1st
1031
dealing_with_jbuf= true;
1032
emb_insideout_nest= false;
1035
Absorb all preceding duplicate-eliminating ranges. Their strategies
1038
for (int prev_range= 0; prev_range < cur_range; prev_range++)
1040
dups_ranges[cur_range].outer_tables |=
1041
dups_ranges[prev_range].outer_tables;
1043
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
1044
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
1049
Check if we are at the end of duplicate-producing range. We are if
1051
1. It's an InsideOut range (which presumes all correlated tables are
1052
in the prefix), and all inner tables are in the join order prefix,
1054
2. It's a DuplicateElimination range (possibly covering several
1055
SJ-nests), and all inner, outer, and correlated tables of all
1056
sj-nests are in the join order prefix.
1058
bool end_of_range= false;
1059
if (emb_insideout_nest &&
1060
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
1062
/* Save that this range is handled with InsideOut: */
1063
dups_ranges[cur_range].strategy= 1;
1066
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
1069
This is a complete range to be handled with either DuplicateWeedout
1072
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
1074
This will hold tables from within the range that need to be put
1075
into the join buffer before we can use the FirstMatch on its tail.
1077
dups_ranges[cur_range].outer_tables= emb_outer_tables &
1084
dups_ranges[cur_range].end_idx= i+1;
1085
emb_sj_map= emb_outer_tables= 0;
1086
emb_insideout_nest= NULL;
1087
dealing_with_jbuf= false;
1088
dups_ranges[++cur_range].strategy= 0;
1093
THD *thd= join->thd;
1094
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
1096
Second pass: setup the chosen strategies
1098
for (int j= 0; j < cur_range; j++)
1100
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
1102
if (dups_ranges[j].strategy == 1) // InsideOut strategy
1104
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
1107
else // DuplicateWeedout strategy
1109
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
1110
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
1111
uint jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
1112
uint jt_null_bits= 0; // # null bits in tuple bytes
1113
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
1114
uint rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
1115
JOIN_TAB *last_outer_tab= tab - 1;
1117
Walk through the range and remember
1118
- tables that need their rowids to be put into temptable
1119
- the last outer table
1121
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1123
if (sj_table_is_included(join, tab))
1125
last_tab->join_tab= tab;
1126
last_tab->rowid_offset= jt_rowid_offset;
1127
jt_rowid_offset += tab->table->file->ref_length;
1128
if (tab->table->maybe_null)
1130
last_tab->null_byte= jt_null_bits / 8;
1131
last_tab->null_bit= jt_null_bits++;
1134
tab->table->prepare_for_position();
1135
tab->rowid_keep_flags= rowid_keep_flags;
1137
cur_map |= tab->table->map;
1138
if (!tab->emb_sj_nest && bitmap_covers(cur_map,
1139
dups_ranges[j].outer_tables))
1140
last_outer_tab= tab;
1143
if (jt_rowid_offset) /* Temptable has at least one rowid */
1145
SJ_TMP_TABLE *sjtbl;
1146
uint tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
1147
if (!(sjtbl= (SJ_TMP_TABLE*)thd->alloc(sizeof(SJ_TMP_TABLE))) ||
1148
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) thd->alloc(tabs_size)))
1150
memcpy(sjtbl->tabs, sjtabs, tabs_size);
1151
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
1152
sjtbl->rowid_len= jt_rowid_offset;
1153
sjtbl->null_bits= jt_null_bits;
1154
sjtbl->null_bytes= (jt_null_bits + 7)/8;
1156
*next_sjtbl_ptr= sjtbl;
1157
next_sjtbl_ptr= &(sjtbl->next);
1161
create_duplicate_weedout_tmp_table(thd,
1166
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
1167
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
1169
tab= last_outer_tab + 1;
1170
jump_to= last_outer_tab;
1173
/* Create the FirstMatch tail */
1174
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1176
if (tab->emb_sj_nest)
1177
tab->do_firstmatch= jump_to;
1186
static void cleanup_sj_tmp_tables(JOIN *join)
1188
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
1189
sj_tbl= sj_tbl->next)
1191
if (sj_tbl->tmp_table)
1193
sj_tbl->tmp_table->free_tmp_table(join->thd);
1196
join->sj_tmp_tables= NULL;
1199
uint make_join_orderinfo(JOIN *join);
1202
global select optimisation.
1205
error code saved in field 'error'
1216
// to prevent double initialization on EXPLAIN
1221
thd_proc_info(thd, "optimizing");
1222
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
1223
unit->select_limit_cnt);
1224
/* select_limit is used to decide if we are likely to scan the whole table */
1225
select_limit= unit->select_limit_cnt;
1226
if (having || (select_options & OPTION_FOUND_ROWS))
1227
select_limit= HA_POS_ERROR;
1228
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
1229
// Ignore errors of execution if option IGNORE present
1230
if (thd->lex->ignore)
1231
thd->lex->current_select->no_error= 1;
1233
#ifdef HAVE_REF_TO_FIELDS // Not done yet
1234
/* Add HAVING to WHERE if possible */
1235
if (having && !group_list && !sum_func_count)
1242
else if ((conds=new Item_cond_and(conds,having)))
1245
Item_cond_and can't be fixed after creation, so we do not check
1248
conds->fix_fields(thd, &conds);
1249
conds->change_ref_to_fields(thd, tables_list);
1250
conds->top_level_item();
1255
SELECT_LEX *sel= thd->lex->current_select;
1256
if (sel->first_cond_optimization)
1259
The following code will allocate the new items in a permanent
1260
MEMROOT for prepared statements and stored procedures.
1262
sel->first_cond_optimization= 0;
1264
/* Convert all outer joins to inner joins if possible */
1265
conds= simplify_joins(this, join_list, conds, true, false);
1266
build_bitmap_for_nested_joins(join_list, 0);
1269
conds= optimize_cond(this, conds, join_list, &cond_value);
1270
if (thd->is_error())
1277
having= optimize_cond(this, having, join_list, &having_value);
1278
if (thd->is_error())
1283
if (select_lex->where)
1284
select_lex->cond_value= cond_value;
1285
if (select_lex->having)
1286
select_lex->having_value= having_value;
1288
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
1289
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
1290
{ /* Impossible cond */
1291
zero_result_cause= having_value == Item::COND_FALSE ?
1292
"Impossible HAVING" : "Impossible WHERE";
1298
/* Optimize count(*), min() and max() */
1299
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
1303
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
1304
to the WHERE conditions,
1305
or 1 if all items were resolved,
1306
or 0, or an error number HA_ERR_...
1308
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
1310
if (res == HA_ERR_KEY_NOT_FOUND)
1312
zero_result_cause= "No matching min/max row";
1323
zero_result_cause= "No matching min/max row";
1327
zero_result_cause= "Select tables optimized away";
1328
tables_list= 0; // All tables resolved
1330
Extract all table-independent conditions and replace the WHERE
1331
clause with them. All other conditions were computed by opt_sum_query
1332
and the MIN/MAX/COUNT function(s) have been replaced by constants,
1333
so there is no need to compute the whole WHERE clause again.
1334
Notice that make_cond_for_table() will always succeed to remove all
1335
computed conditions, because opt_sum_query() is applicable only to
1337
Preserve conditions for EXPLAIN.
1339
if (conds && !(thd->lex->describe & DESCRIBE_EXTENDED))
1341
COND *table_independent_conds=
1342
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
1343
conds= table_independent_conds;
1352
error= -1; // Error is sent to client
1353
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
1355
/* Calculate how to do the join */
1356
thd_proc_info(thd, "statistics");
1357
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
1358
thd->is_fatal_error)
1363
/* Remove distinct if only const tables */
1364
select_distinct= select_distinct && (const_tables != tables);
1365
thd_proc_info(thd, "preparing");
1366
if (result->initialize_tables(this))
1368
return(1); // error == -1
1370
if (const_table_map != found_const_table_map &&
1371
!(select_options & SELECT_DESCRIBE) &&
1373
!(conds->used_tables() & RAND_TABLE_BIT) ||
1374
select_lex->master_unit() == &thd->lex->unit)) // upper level SELECT
1376
zero_result_cause= "no matching row in const table";
1380
if (!(thd->options & OPTION_BIG_SELECTS) &&
1381
best_read > (double) thd->variables.max_join_size &&
1382
!(select_options & SELECT_DESCRIBE))
1383
{ /* purecov: inspected */
1384
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
1388
if (const_tables && !thd->locked_tables &&
1389
!(select_options & SELECT_NO_UNLOCK))
1390
mysql_unlock_some_tables(thd, table, const_tables);
1391
if (!conds && outer_join)
1393
/* Handle the case where we have an OUTER JOIN without a WHERE */
1394
conds=new Item_int((int64_t) 1,1); // Always true
1396
select= make_select(*table, const_table_map,
1397
const_table_map, conds, 1, &error);
1399
{ /* purecov: inspected */
1400
error= -1; /* purecov: inspected */
1404
reset_nj_counters(join_list);
1405
make_outerjoin_info(this);
1408
Among the equal fields belonging to the same multiple equality
1409
choose the one that is to be retrieved first and substitute
1410
all references to these in where condition for a reference for
1415
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
1416
conds->update_used_tables();
1420
Permorm the the optimization on fields evaluation mentioned above
1421
for all on expressions.
1423
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
1425
if (*tab->on_expr_ref)
1427
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
1430
(*tab->on_expr_ref)->update_used_tables();
1434
if (conds &&!outer_join && const_table_map != found_const_table_map &&
1435
(select_options & SELECT_DESCRIBE) &&
1436
select_lex->master_unit() == &thd->lex->unit) // upper level SELECT
1438
conds=new Item_int((int64_t) 0,1); // Always false
1440
if (make_join_select(this, select, conds))
1443
"Impossible WHERE noticed after reading const tables";
1444
return(0); // error == 0
1447
error= -1; /* if goto err */
1449
/* Optimize distinct away if possible */
1451
ORDER *org_order= order;
1452
order=remove_const(this, order,conds,1, &simple_order);
1453
if (thd->is_error())
1460
If we are using ORDER BY NULL or ORDER BY const_expression,
1461
return result in any order (even if we are using a GROUP BY)
1463
if (!order && org_order)
1467
Check if we can optimize away GROUP BY/DISTINCT.
1468
We can do that if there are no aggregate functions, the
1469
fields in DISTINCT clause (if present) and/or columns in GROUP BY
1470
(if present) contain direct references to all key parts of
1471
an unique index (in whatever order) and if the key parts of the
1472
unique index cannot contain NULLs.
1473
Note that the unique keys for DISTINCT and GROUP BY should not
1474
be the same (as long as they are unique).
1476
The FROM clause must contain a single non-constant table.
1478
if (tables - const_tables == 1 && (group_list || select_distinct) &&
1479
!tmp_table_param.sum_func_count &&
1480
(!join_tab[const_tables].select ||
1481
!join_tab[const_tables].select->quick ||
1482
join_tab[const_tables].select->quick->get_type() !=
1483
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
1486
list_contains_unique_index(join_tab[const_tables].table,
1487
find_field_in_order_list,
1488
(void *) group_list))
1491
We have found that grouping can be removed since groups correspond to
1492
only one row anyway, but we still have to guarantee correct result
1493
order. The line below effectively rewrites the query from GROUP BY
1494
<fields> to ORDER BY <fields>. There are two exceptions:
1495
- if skip_sort_order is set (see above), then we can simply skip
1497
- we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'
1498
with the GROUP BY ones, i.e. either one is a prefix of another.
1499
We only check if the ORDER BY is a prefix of GROUP BY. In this case
1500
test_if_subpart() copies the ASC/DESC attributes from the original
1502
If GROUP BY is a prefix of ORDER BY, then it is safe to leave
1505
if (!order || test_if_subpart(group_list, order))
1506
order= skip_sort_order ? 0 : group_list;
1508
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
1509
rewritten to IGNORE INDEX FOR ORDER BY(fields).
1511
join_tab->table->keys_in_use_for_order_by=
1512
join_tab->table->keys_in_use_for_group_by;
1516
if (select_distinct &&
1517
list_contains_unique_index(join_tab[const_tables].table,
1518
find_field_in_item_list,
1519
(void *) &fields_list))
1524
if (group_list || tmp_table_param.sum_func_count)
1526
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
1529
else if (select_distinct && tables - const_tables == 1)
1532
We are only using one table. In this case we change DISTINCT to a
1534
- The GROUP BY can be done through indexes (no sort) and the ORDER
1535
BY only uses selected fields.
1536
(In this case we can later optimize away GROUP BY and ORDER BY)
1537
- We are scanning the whole table without LIMIT
1539
- We are using CALC_FOUND_ROWS
1540
- We are using an ORDER BY that can't be optimized away.
1542
We don't want to use this optimization when we are using LIMIT
1543
because in this case we can just create a temporary table that
1544
holds LIMIT rows and stop when this table is full.
1546
JOIN_TAB *tab= &join_tab[const_tables];
1547
bool all_order_fields_used;
1549
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
1550
&tab->table->keys_in_use_for_order_by);
1551
if ((group_list=create_distinct_group(thd, select_lex->ref_pointer_array,
1552
order, fields_list, all_fields,
1553
&all_order_fields_used)))
1555
bool skip_group= (skip_sort_order &&
1556
test_if_skip_sort_order(tab, group_list, select_limit, 1,
1557
&tab->table->keys_in_use_for_group_by) != 0);
1558
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
1559
if ((skip_group && all_order_fields_used) ||
1560
select_limit == HA_POS_ERROR ||
1561
(order && !skip_sort_order))
1563
/* Change DISTINCT to GROUP BY */
1566
if (all_order_fields_used)
1568
if (order && skip_sort_order)
1571
Force MySQL to read the table in sorted order to get result in
1574
tmp_table_param.quick_group=0;
1578
group=1; // For end_write_group
1583
else if (thd->is_fatal_error) // End of memory
1588
ORDER *old_group_list;
1589
group_list= remove_const(this, (old_group_list= group_list), conds,
1590
rollup.state == ROLLUP::STATE_NONE,
1592
if (thd->is_error())
1597
if (old_group_list && !group_list)
1600
if (!group_list && group)
1602
order=0; // The output has only one row
1604
select_distinct= 0; // No need in distinct for 1 row
1605
group_optimized_away= 1;
1608
calc_group_buffer(this, group_list);
1609
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
1611
if (test_if_subpart(group_list, order) ||
1612
(!group_list && tmp_table_param.sum_func_count))
1615
// Can't use sort on head table if using row cache
1625
Check if we need to create a temporary table.
1626
This has to be done if all tables are not already read (const tables)
1627
and one of the following conditions holds:
1628
- We are using DISTINCT (simple distinct's are already optimized away)
1629
- We are using an ORDER BY or GROUP BY on fields not in the first table
1630
- We are using different ORDER BY and GROUP BY orders
1631
- The user wants us to buffer the result.
1633
need_tmp= (const_tables != tables &&
1634
((select_distinct || !simple_order || !simple_group) ||
1635
(group_list && order) ||
1636
test(select_options & OPTION_BUFFER_RESULT)));
1638
uint no_jbuf_after= make_join_orderinfo(this);
1639
uint64_t select_opts_for_readinfo=
1640
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
1642
sj_tmp_tables= NULL;
1643
if (!select_lex->sj_nests.is_empty())
1644
setup_semijoin_dups_elimination(this, select_opts_for_readinfo,
1647
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1648
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1651
/* Create all structures needed for materialized subquery execution. */
1652
if (setup_subquery_materialization())
1656
is this simple IN subquery?
1658
if (!group_list && !order &&
1659
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1660
tables == 1 && conds &&
1666
if (join_tab[0].type == JT_EQ_REF &&
1667
join_tab[0].ref.items[0]->name == in_left_expr_name)
1669
remove_subq_pushed_predicates(&where);
1670
save_index_subquery_explain_info(join_tab, where);
1671
join_tab[0].type= JT_UNIQUE_SUBQUERY;
1675
subselect_uniquesubquery_engine(thd,
1680
else if (join_tab[0].type == JT_REF &&
1681
join_tab[0].ref.items[0]->name == in_left_expr_name)
1683
remove_subq_pushed_predicates(&where);
1684
save_index_subquery_explain_info(join_tab, where);
1685
join_tab[0].type= JT_INDEX_SUBQUERY;
1689
subselect_indexsubquery_engine(thd,
1696
} else if (join_tab[0].type == JT_REF_OR_NULL &&
1697
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1698
having->name == in_having_cond)
1700
join_tab[0].type= JT_INDEX_SUBQUERY;
1702
conds= remove_additional_cond(conds);
1703
save_index_subquery_explain_info(join_tab, conds);
1705
change_engine(new subselect_indexsubquery_engine(thd,
1715
Need to tell handlers that to play it safe, it should fetch all
1716
columns of the primary key of the tables: this is because MySQL may
1717
build row pointers for the rows, and for all columns of the primary key
1718
the read set has not necessarily been set by the server code.
1720
if (need_tmp || select_distinct || group_list || order)
1722
for (uint i = const_tables; i < tables; i++)
1723
join_tab[i].table->prepare_for_position();
1726
if (const_tables != tables)
1729
Because filesort always does a full table scan or a quick range scan
1730
we must add the removed reference to the select for the table.
1731
We only need to do this when we have a simple_order or simple_group
1732
as in other cases the join is done before the sort.
1734
if ((order || group_list) &&
1735
(join_tab[const_tables].type != JT_ALL) &&
1736
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
1737
((order && simple_order) || (group_list && simple_group)))
1739
if (add_ref_to_table_cond(thd,&join_tab[const_tables])) {
1744
if (!(select_options & SELECT_BIG_RESULT) &&
1747
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1748
unit->select_limit_cnt, 0,
1749
&join_tab[const_tables].table->
1750
keys_in_use_for_group_by))) ||
1752
tmp_table_param.quick_group)
1754
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1759
Force using of tmp table if sorting by a SP or UDF function due to
1760
their expensive and probably non-deterministic nature.
1762
for (ORDER *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1764
Item *item= *tmp_order->item;
1765
if (item->is_expensive())
1767
/* Force tmp table without sort */
1768
need_tmp=1; simple_order=simple_group=0;
1776
if (select_options & SELECT_DESCRIBE)
1784
The loose index scan access method guarantees that all grouping or
1785
duplicate row elimination (for distinct) is already performed
1786
during data retrieval, and that all MIN/MAX functions are already
1787
computed for each group. Thus all MIN/MAX functions should be
1788
treated as regular functions, and there is no need to perform
1789
grouping in the main execution loop.
1790
Notice that currently loose index scan is applicable only for
1791
single table queries, thus it is sufficient to test only the first
1792
join_tab element of the plan for its access method.
1794
if (join_tab->is_using_loose_index_scan())
1795
tmp_table_param.precomputed_group_by= true;
1797
/* Create a tmp table if distinct or if the sort is too complicated */
1800
thd_proc_info(thd, "Creating tmp table");
1802
init_items_ref_array();
1804
tmp_table_param.hidden_field_count= (all_fields.elements -
1805
fields_list.elements);
1806
ORDER *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1809
Pushing LIMIT to the temporary table creation is not applicable
1810
when there is ORDER BY or GROUP BY or there is no GROUP BY, but
1811
there are aggregate functions, because in all these cases we need
1814
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1816
!thd->lex->current_select->with_sum_func) ?
1817
select_limit : HA_POS_ERROR;
1819
if (!(exec_tmp_table1=
1820
create_tmp_table(thd, &tmp_table_param, all_fields,
1822
group_list ? 0 : select_distinct,
1823
group_list && simple_group,
1832
We don't have to store rows in temp table that doesn't match HAVING if:
1833
- we are sorting the table and writing complete group rows to the
1835
- We are using DISTINCT without resolving the distinct as a GROUP BY
1838
If having is not handled here, it will be checked before the row
1839
is sent to the client.
1842
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1845
/* if group or order on first table, sort first */
1846
if (group_list && simple_group)
1848
thd_proc_info(thd, "Sorting for group");
1849
if (create_sort_index(thd, this, group_list,
1850
HA_POS_ERROR, HA_POS_ERROR, false) ||
1851
alloc_group_fields(this, group_list) ||
1852
make_sum_func_list(all_fields, fields_list, 1) ||
1853
setup_sum_funcs(thd, sum_funcs))
1861
if (make_sum_func_list(all_fields, fields_list, 0) ||
1862
setup_sum_funcs(thd, sum_funcs))
1867
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1869
thd_proc_info(thd, "Sorting for order");
1870
if (create_sort_index(thd, this, order,
1871
HA_POS_ERROR, HA_POS_ERROR, true))
1880
Optimize distinct when used on some of the tables
1881
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1882
In this case we can stop scanning t2 when we have found one t1.a
1885
if (exec_tmp_table1->distinct)
1887
table_map used_tables= thd->used_tables;
1888
JOIN_TAB *last_join_tab= join_tab+tables-1;
1891
if (used_tables & last_join_tab->table->map)
1893
last_join_tab->not_used_in_distinct=1;
1894
} while (last_join_tab-- != join_tab);
1895
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1896
if (order && skip_sort_order)
1898
/* Should always succeed */
1899
if (test_if_skip_sort_order(&join_tab[const_tables],
1900
order, unit->select_limit_cnt, 0,
1901
&join_tab[const_tables].table->
1902
keys_in_use_for_order_by))
1908
If this join belongs to an uncacheable subquery save
1911
if (select_lex->uncacheable && !is_top_level_join() &&
1912
init_save_join_tab())
1913
return(-1); /* purecov: inspected */
1922
Restore values in temporary join.
1924
void JOIN::restore_tmp()
1926
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1933
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1934
select_lex->offset_limit->val_uint() :
1939
if (exec_tmp_table1)
1941
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1942
exec_tmp_table1->file->ha_delete_all_rows();
1943
free_io_cache(exec_tmp_table1);
1944
filesort_free_buffers(exec_tmp_table1,0);
1946
if (exec_tmp_table2)
1948
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1949
exec_tmp_table2->file->ha_delete_all_rows();
1950
free_io_cache(exec_tmp_table2);
1951
filesort_free_buffers(exec_tmp_table2,0);
1954
set_items_ref_array(items0);
1957
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1962
/* Reset of sum functions */
1965
Item_sum *func, **func_ptr= sum_funcs;
1966
while ((func= *(func_ptr++)))
1974
@brief Save the original join layout
1976
@details Saves the original join layout so it can be reused in
1977
re-execution and for EXPLAIN.
1979
@return Operation status
1981
@retval 1 error occurred.
1985
JOIN::init_save_join_tab()
1987
if (!(tmp_join= (JOIN*)thd->alloc(sizeof(JOIN))))
1988
return 1; /* purecov: inspected */
1989
error= 0; // Ensure that tmp_join.error= 0
1996
JOIN::save_join_tab()
1998
if (!join_tab_save && select_lex->master_unit()->uncacheable)
2000
if (!(join_tab_save= (JOIN_TAB*)thd->memdup((uchar*) join_tab,
2001
sizeof(JOIN_TAB) * tables)))
2012
Note, that create_sort_index calls test_if_skip_sort_order and may
2013
finally replace sorting with index scan if there is a LIMIT clause in
2014
the query. It's never shown in EXPLAIN!
2017
When can we have here thd->net.report_error not zero?
2022
List<Item> *columns_list= &fields_list;
2025
thd_proc_info(thd, "executing");
2027
(void) result->prepare2(); // Currently, this cannot fail.
2029
if (!tables_list && (tables || !select_lex->with_sum_func))
2030
{ // Only test of functions
2031
if (select_options & SELECT_DESCRIBE)
2032
select_describe(this, false, false, false,
2033
(zero_result_cause?zero_result_cause:"No tables used"));
2036
result->send_fields(*columns_list,
2037
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2039
We have to test for 'conds' here as the WHERE may not be constant
2040
even if we don't have any tables for prepared statements or if
2041
conds uses something like 'rand()'.
2043
if (cond_value != Item::COND_FALSE &&
2044
(!conds || conds->val_int()) &&
2045
(!having || having->val_int()))
2047
if (do_send_rows && result->send_data(fields_list))
2051
error= (int) result->send_eof();
2052
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 :
2053
thd->sent_row_count);
2058
error=(int) result->send_eof();
2062
/* Single select (without union) always returns 0 or 1 row */
2063
thd->limit_found_rows= send_records;
2064
thd->examined_row_count= 0;
2068
Don't reset the found rows count if there're no tables as
2069
FOUND_ROWS() may be called. Never reset the examined row count here.
2070
It must be accumulated from all join iterations of all join parts.
2073
thd->limit_found_rows= 0;
2075
if (zero_result_cause)
2077
(void) return_zero_rows(this, result, select_lex->leaf_tables,
2079
send_row_on_empty_set(),
2086
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) &&
2087
get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
2090
if (select_options & SELECT_DESCRIBE)
2093
Check if we managed to optimize ORDER BY away and don't use temporary
2094
table to resolve ORDER BY: in that case, we only may need to do
2095
filesort for GROUP BY.
2097
if (!order && !no_order && (!skip_sort_order || !need_tmp))
2100
Reset 'order' to 'group_list' and reinit variables describing
2104
simple_order= simple_group;
2108
(order != group_list || !(select_options & SELECT_BIG_RESULT)) &&
2109
(const_tables == tables ||
2110
((simple_order || skip_sort_order) &&
2111
test_if_skip_sort_order(&join_tab[const_tables], order,
2113
&join_tab[const_tables].table->
2114
keys_in_use_for_query))))
2117
select_describe(this, need_tmp,
2118
order != 0 && !skip_sort_order,
2120
!tables ? "No tables used" : NullS);
2124
JOIN *curr_join= this;
2125
List<Item> *curr_all_fields= &all_fields;
2126
List<Item> *curr_fields_list= &fields_list;
2127
TABLE *curr_tmp_table= 0;
2129
Initialize examined rows here because the values from all join parts
2130
must be accumulated in examined_row_count. Hence every join
2131
iteration must count from zero.
2133
curr_join->examined_rows= 0;
2135
/* Create a tmp table if distinct or if the sort is too complicated */
2141
We are in a non cacheable sub query. Get the saved join structure
2143
(curr_join may have been modified during last exection and we need
2146
curr_join= tmp_join;
2148
curr_tmp_table= exec_tmp_table1;
2150
/* Copy data to the temporary table */
2151
thd_proc_info(thd, "Copying to tmp table");
2152
if (!curr_join->sort_and_group &&
2153
curr_join->const_tables != curr_join->tables)
2154
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2155
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2160
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
2162
if (curr_join->having)
2163
curr_join->having= curr_join->tmp_having= 0; // Allready done
2165
/* Change sum_fields reference to calculated fields in tmp_table */
2166
curr_join->all_fields= *curr_all_fields;
2169
items1= items0 + all_fields.elements;
2170
if (sort_and_group || curr_tmp_table->group)
2172
if (change_to_use_tmp_fields(thd, items1,
2173
tmp_fields_list1, tmp_all_fields1,
2174
fields_list.elements, all_fields))
2179
if (change_refs_to_tmp_fields(thd, items1,
2180
tmp_fields_list1, tmp_all_fields1,
2181
fields_list.elements, all_fields))
2184
curr_join->tmp_all_fields1= tmp_all_fields1;
2185
curr_join->tmp_fields_list1= tmp_fields_list1;
2186
curr_join->items1= items1;
2188
curr_all_fields= &tmp_all_fields1;
2189
curr_fields_list= &tmp_fields_list1;
2190
curr_join->set_items_ref_array(items1);
2192
if (sort_and_group || curr_tmp_table->group)
2194
curr_join->tmp_table_param.field_count+=
2195
curr_join->tmp_table_param.sum_func_count+
2196
curr_join->tmp_table_param.func_count;
2197
curr_join->tmp_table_param.sum_func_count=
2198
curr_join->tmp_table_param.func_count= 0;
2202
curr_join->tmp_table_param.field_count+=
2203
curr_join->tmp_table_param.func_count;
2204
curr_join->tmp_table_param.func_count= 0;
2207
if (curr_tmp_table->group)
2208
{ // Already grouped
2209
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
2210
curr_join->order= curr_join->group_list; /* order by group */
2211
curr_join->group_list= 0;
2215
If we have different sort & group then we must sort the data by group
2216
and copy it to another tmp table
2217
This code is also used if we are using distinct something
2218
we haven't been able to store in the temporary table yet
2219
like SEC_TO_TIME(SUM(...)).
2222
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct)) || (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
2223
{ /* Must copy to another table */
2224
/* Free first data from old join */
2225
curr_join->join_free();
2226
if (make_simple_join(curr_join, curr_tmp_table))
2228
calc_group_buffer(curr_join, group_list);
2229
count_field_types(select_lex, &curr_join->tmp_table_param,
2230
curr_join->tmp_all_fields1,
2231
curr_join->select_distinct && !curr_join->group_list);
2232
curr_join->tmp_table_param.hidden_field_count=
2233
(curr_join->tmp_all_fields1.elements-
2234
curr_join->tmp_fields_list1.elements);
2237
if (exec_tmp_table2)
2238
curr_tmp_table= exec_tmp_table2;
2241
/* group data to new table */
2244
If the access method is loose index scan then all MIN/MAX
2245
functions are precomputed, and should be treated as regular
2246
functions. See extended comment in JOIN::exec.
2248
if (curr_join->join_tab->is_using_loose_index_scan())
2249
curr_join->tmp_table_param.precomputed_group_by= true;
2251
if (!(curr_tmp_table=
2252
exec_tmp_table2= create_tmp_table(thd,
2253
&curr_join->tmp_table_param,
2256
curr_join->select_distinct &&
2257
!curr_join->group_list,
2258
1, curr_join->select_options,
2262
curr_join->exec_tmp_table2= exec_tmp_table2;
2264
if (curr_join->group_list)
2266
thd_proc_info(thd, "Creating sort index");
2267
if (curr_join->join_tab == join_tab && save_join_tab())
2271
if (create_sort_index(thd, curr_join, curr_join->group_list,
2272
HA_POS_ERROR, HA_POS_ERROR, false) ||
2273
make_group_fields(this, curr_join))
2277
sortorder= curr_join->sortorder;
2280
thd_proc_info(thd, "Copying to group table");
2282
if (curr_join != this)
2286
curr_join->sum_funcs= sum_funcs2;
2287
curr_join->sum_funcs_end= sum_funcs_end2;
2291
curr_join->alloc_func_list();
2292
sum_funcs2= curr_join->sum_funcs;
2293
sum_funcs_end2= curr_join->sum_funcs_end;
2296
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2299
curr_join->group_list= 0;
2300
if (!curr_join->sort_and_group &&
2301
curr_join->const_tables != curr_join->tables)
2302
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2303
if (setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) ||
2304
(tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2309
end_read_record(&curr_join->join_tab->read_record);
2310
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
2311
curr_join->join_tab[0].table= 0; // Table is freed
2313
// No sum funcs anymore
2316
items2= items1 + all_fields.elements;
2317
if (change_to_use_tmp_fields(thd, items2,
2318
tmp_fields_list2, tmp_all_fields2,
2319
fields_list.elements, tmp_all_fields1))
2321
curr_join->tmp_fields_list2= tmp_fields_list2;
2322
curr_join->tmp_all_fields2= tmp_all_fields2;
2324
curr_fields_list= &curr_join->tmp_fields_list2;
2325
curr_all_fields= &curr_join->tmp_all_fields2;
2326
curr_join->set_items_ref_array(items2);
2327
curr_join->tmp_table_param.field_count+=
2328
curr_join->tmp_table_param.sum_func_count;
2329
curr_join->tmp_table_param.sum_func_count= 0;
2331
if (curr_tmp_table->distinct)
2332
curr_join->select_distinct=0; /* Each row is unique */
2334
curr_join->join_free(); /* Free quick selects */
2335
if (curr_join->select_distinct && ! curr_join->group_list)
2337
thd_proc_info(thd, "Removing duplicates");
2338
if (curr_join->tmp_having)
2339
curr_join->tmp_having->update_used_tables();
2340
if (remove_duplicates(curr_join, curr_tmp_table,
2341
*curr_fields_list, curr_join->tmp_having))
2343
curr_join->tmp_having=0;
2344
curr_join->select_distinct=0;
2346
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
2347
if (make_simple_join(curr_join, curr_tmp_table))
2349
calc_group_buffer(curr_join, curr_join->group_list);
2350
count_field_types(select_lex, &curr_join->tmp_table_param,
2351
*curr_all_fields, 0);
2355
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
2357
if (make_group_fields(this, curr_join))
2364
init_items_ref_array();
2365
items3= ref_pointer_array + (all_fields.elements*4);
2366
setup_copy_fields(thd, &curr_join->tmp_table_param,
2367
items3, tmp_fields_list3, tmp_all_fields3,
2368
curr_fields_list->elements, *curr_all_fields);
2369
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
2370
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
2371
tmp_table_param.save_copy_field_end=
2372
curr_join->tmp_table_param.copy_field_end;
2373
curr_join->tmp_all_fields3= tmp_all_fields3;
2374
curr_join->tmp_fields_list3= tmp_fields_list3;
2378
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
2379
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
2380
curr_join->tmp_table_param.copy_field_end=
2381
tmp_table_param.save_copy_field_end;
2383
curr_fields_list= &tmp_fields_list3;
2384
curr_all_fields= &tmp_all_fields3;
2385
curr_join->set_items_ref_array(items3);
2387
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2389
setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) ||
2390
thd->is_fatal_error)
2393
if (curr_join->group_list || curr_join->order)
2395
thd_proc_info(thd, "Sorting result");
2396
/* If we have already done the group, add HAVING to sorted table */
2397
if (curr_join->tmp_having && ! curr_join->group_list &&
2398
! curr_join->sort_and_group)
2400
// Some tables may have been const
2401
curr_join->tmp_having->update_used_tables();
2402
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
2403
table_map used_tables= (curr_join->const_table_map |
2404
curr_table->table->map);
2406
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having,
2409
if (sort_table_cond)
2411
if (!curr_table->select)
2412
if (!(curr_table->select= new SQL_SELECT))
2414
if (!curr_table->select->cond)
2415
curr_table->select->cond= sort_table_cond;
2416
else // This should never happen
2418
if (!(curr_table->select->cond=
2419
new Item_cond_and(curr_table->select->cond,
2423
Item_cond_and do not need fix_fields for execution, its parameters
2424
are fixed or do not need fix_fields, too
2426
curr_table->select->cond->quick_fix_field();
2428
curr_table->select_cond= curr_table->select->cond;
2429
curr_table->select_cond->top_level_item();
2430
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
2437
curr_join->select_limit= HA_POS_ERROR;
2441
We can abort sorting after thd->select_limit rows if we there is no
2442
WHERE clause for any tables after the sorted one.
2444
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
2445
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
2446
for (; curr_table < end_table ; curr_table++)
2449
table->keyuse is set in the case there was an original WHERE clause
2450
on the table that was optimized away.
2452
if (curr_table->select_cond ||
2453
(curr_table->keyuse && !curr_table->first_inner))
2455
/* We have to sort all rows */
2456
curr_join->select_limit= HA_POS_ERROR;
2461
if (curr_join->join_tab == join_tab && save_join_tab())
2466
Here we sort rows for ORDER BY/GROUP BY clause, if the optimiser
2467
chose FILESORT to be faster than INDEX SCAN or there is no
2468
suitable index present.
2469
Note, that create_sort_index calls test_if_skip_sort_order and may
2470
finally replace sorting with index scan if there is a LIMIT clause in
2471
the query. XXX: it's never shown in EXPLAIN!
2472
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
2474
if (create_sort_index(thd, curr_join,
2475
curr_join->group_list ?
2476
curr_join->group_list : curr_join->order,
2477
curr_join->select_limit,
2478
(select_options & OPTION_FOUND_ROWS ?
2479
HA_POS_ERROR : unit->select_limit_cnt),
2480
curr_join->group_list ? true : false))
2482
sortorder= curr_join->sortorder;
2483
if (curr_join->const_tables != curr_join->tables &&
2484
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
2487
If no IO cache exists for the first table then we are using an
2488
INDEX SCAN and no filesort. Thus we should not remove the sorted
2489
attribute on the INDEX SCAN.
2495
/* XXX: When can we have here thd->is_error() not zero? */
2496
if (thd->is_error())
2498
error= thd->is_error();
2501
curr_join->having= curr_join->tmp_having;
2502
curr_join->fields= curr_fields_list;
2505
thd_proc_info(thd, "Sending data");
2506
result->send_fields(*curr_fields_list,
2507
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2508
error= do_select(curr_join, curr_fields_list, NULL);
2509
thd->limit_found_rows= curr_join->send_records;
2512
/* Accumulate the counts from all join iterations of all join parts. */
2513
thd->examined_row_count+= curr_join->examined_rows;
2516
With EXPLAIN EXTENDED we have to restore original ref_array
2517
for a derived table which is always materialized.
2518
Otherwise we would not be able to print the query correctly.
2521
(thd->lex->describe & DESCRIBE_EXTENDED) &&
2522
select_lex->linkage == DERIVED_TABLE_TYPE)
2523
set_items_ref_array(items0);
2533
Return error that hold JOIN.
2539
select_lex->join= 0;
2543
if (join_tab != tmp_join->join_tab)
2545
JOIN_TAB *tab, *end;
2546
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
2549
tmp_join->tmp_join= 0;
2550
tmp_table_param.copy_field=0;
2551
return(tmp_join->destroy());
2556
if (exec_tmp_table1)
2557
exec_tmp_table1->free_tmp_table(thd);
2558
if (exec_tmp_table2)
2559
exec_tmp_table2->free_tmp_table(thd);
2561
delete_dynamic(&keyuse);
318
2568
An entry point to single-unit select (a select without UNION).
320
@param session thread Cursor
2570
@param thd thread handler
321
2571
@param rref_pointer_array a reference to ref_pointer_array of
322
2572
the top-level select_lex for this query
323
2573
@param tables list of all tables used in this query.
324
2574
The tables have been pre-opened.
325
@param wild_num number of wildcards used in the top level
2575
@param wild_num number of wildcards used in the top level
326
2576
select of this query.
327
2577
For example statement
328
2578
SELECT *, t1.*, catalog.t2.* FROM t0, t1, t2;
2751
Convert a subquery predicate into a TABLE_LIST semi-join nest
2754
convert_subq_to_sj()
2755
parent_join Parent join, the one that has subq_pred in its WHERE/ON
2757
subq_pred Subquery predicate to be converted
2760
Convert a subquery predicate into a TABLE_LIST semi-join nest. All the
2761
prerequisites are already checked, so the conversion is always successfull.
2763
Prepared Statements: the transformation is permanent:
2764
- Changes in TABLE_LIST structures are naturally permanent
2765
- Item tree changes are performed on statement MEM_ROOT:
2766
= we activate statement MEM_ROOT
2767
= this function is called before the first fix_prepare_information
2770
This is intended because the criteria for subquery-to-sj conversion remain
2771
constant for the lifetime of the Prepared Statement.
2775
true Out of memory error
2778
bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
2780
SELECT_LEX *parent_lex= parent_join->select_lex;
2781
TABLE_LIST *emb_tbl_nest= NULL;
2782
List<TABLE_LIST> *emb_join_list= &parent_lex->top_join_list;
2783
THD *thd= parent_join->thd;
2786
1. Find out where to put the predicate into.
2787
Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
2789
if ((void*)subq_pred->expr_join_nest != (void*)1)
2791
if (subq_pred->expr_join_nest->nested_join)
2796
... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
2798
The sj-nest will be inserted into the brackets nest.
2800
emb_tbl_nest= subq_pred->expr_join_nest;
2801
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2803
else if (!subq_pred->expr_join_nest->outer_join)
2808
... INNER JOIN tblX ON (subquery AND whatever) ...
2810
The sj-nest will be tblX's "sibling", i.e. another child of its
2811
parent. This is ok because tblX is joined as an inner join.
2813
emb_tbl_nest= subq_pred->expr_join_nest->embedding;
2815
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2817
else if (!subq_pred->expr_join_nest->nested_join)
2819
TABLE_LIST *outer_tbl= subq_pred->expr_join_nest;
2820
TABLE_LIST *wrap_nest;
2824
... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
2826
we'll need to convert it into:
2828
... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
2830
|<----- wrap_nest ---->|
2832
Q: other subqueries may be pointing to this element. What to do?
2833
A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
2834
But we'll need to fix other pointers.
2835
A2: Another way: have TABLE_LIST::next_ptr so the following
2836
subqueries know the table has been nested.
2837
A3: changes in the TABLE_LIST::outer_join will make everything work
2840
if (!(wrap_nest= alloc_join_nest(parent_join->thd)))
2844
wrap_nest->embedding= outer_tbl->embedding;
2845
wrap_nest->join_list= outer_tbl->join_list;
2846
wrap_nest->alias= (char*) "(sj-wrap)";
2848
wrap_nest->nested_join->join_list.empty();
2849
wrap_nest->nested_join->join_list.push_back(outer_tbl);
2851
outer_tbl->embedding= wrap_nest;
2852
outer_tbl->join_list= &wrap_nest->nested_join->join_list;
2855
wrap_nest will take place of outer_tbl, so move the outer join flag
2858
wrap_nest->outer_join= outer_tbl->outer_join;
2859
outer_tbl->outer_join= 0;
2861
wrap_nest->on_expr= outer_tbl->on_expr;
2862
outer_tbl->on_expr= NULL;
2864
List_iterator<TABLE_LIST> li(*wrap_nest->join_list);
2868
if (tbl == outer_tbl)
2870
li.replace(wrap_nest);
2875
Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
2876
semi-join nest into it
2878
emb_join_list= &wrap_nest->nested_join->join_list;
2879
emb_tbl_nest= wrap_nest;
2883
TABLE_LIST *sj_nest;
2884
NESTED_JOIN *nested_join;
2885
if (!(sj_nest= alloc_join_nest(parent_join->thd)))
2889
nested_join= sj_nest->nested_join;
2891
sj_nest->join_list= emb_join_list;
2892
sj_nest->embedding= emb_tbl_nest;
2893
sj_nest->alias= (char*) "(sj-nest)";
2894
/* Nests do not participate in those 'chains', so: */
2895
/* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
2896
emb_join_list->push_back(sj_nest);
2899
nested_join->used_tables and nested_join->not_null_tables are
2900
initialized in simplify_joins().
2904
2. Walk through subquery's top list and set 'embedding' to point to the
2907
st_select_lex *subq_lex= subq_pred->unit->first_select();
2908
nested_join->join_list.empty();
2909
List_iterator_fast<TABLE_LIST> li(subq_lex->top_join_list);
2910
TABLE_LIST *tl, *last_leaf;
2913
tl->embedding= sj_nest;
2914
tl->join_list= &nested_join->join_list;
2915
nested_join->join_list.push_back(tl);
2919
Reconnect the next_leaf chain.
2920
TODO: Do we have to put subquery's tables at the end of the chain?
2921
Inserting them at the beginning would be a bit faster.
2922
NOTE: We actually insert them at the front! That's because the order is
2923
reversed in this list.
2925
for (tl= parent_lex->leaf_tables; tl->next_leaf; tl= tl->next_leaf) {};
2926
tl->next_leaf= subq_lex->leaf_tables;
2930
Same as above for next_local chain
2931
(a theory: a next_local chain always starts with ::leaf_tables
2932
because view's tables are inserted after the view)
2934
for (tl= parent_lex->leaf_tables; tl->next_local; tl= tl->next_local) {};
2935
tl->next_local= subq_lex->leaf_tables;
2937
/* A theory: no need to re-connect the next_global chain */
2939
/* 3. Remove the original subquery predicate from the WHERE/ON */
2941
// The subqueries were replaced for Item_int(1) earlier
2942
subq_pred->exec_method= Item_in_subselect::SEMI_JOIN; // for subsequent executions
2943
/*TODO: also reset the 'with_subselect' there. */
2945
/* n. Adjust the parent_join->tables counter */
2946
uint table_no= parent_join->tables;
2947
/* n. Walk through child's tables and adjust table->map */
2948
for (tl= subq_lex->leaf_tables; tl; tl= tl->next_leaf, table_no++)
2950
tl->table->tablenr= table_no;
2951
tl->table->map= ((table_map)1) << table_no;
2952
SELECT_LEX *old_sl= tl->select_lex;
2953
tl->select_lex= parent_join->select_lex;
2954
for(TABLE_LIST *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)
2955
emb->select_lex= parent_join->select_lex;
2957
parent_join->tables += subq_lex->join->tables;
2960
Put the subquery's WHERE into semi-join's sj_on_expr
2961
Add the subquery-induced equalities too.
2963
SELECT_LEX *save_lex= thd->lex->current_select;
2964
thd->lex->current_select=subq_lex;
2965
if (!subq_pred->left_expr->fixed &&
2966
subq_pred->left_expr->fix_fields(thd, &subq_pred->left_expr))
2968
thd->lex->current_select=save_lex;
2970
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
2971
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables() |
2972
subq_pred->left_expr->used_tables();
2973
sj_nest->sj_on_expr= subq_lex->where;
2976
Create the IN-equalities and inject them into semi-join's ON expression.
2977
Additionally, for InsideOut strategy
2978
- Record the number of IN-equalities.
2979
- Create list of pointers to (oe1, ..., ieN). We'll need the list to
2980
see which of the expressions are bound and which are not (for those
2981
we'll produce a distinct stream of (ie_i1,...ie_ik).
2983
(TODO: can we just create a list of pointers and hope the expressions
2984
will not substitute themselves on fix_fields()? or we need to wrap
2985
them into Item_direct_view_refs and store pointers to those. The
2986
pointers to Item_direct_view_refs are guaranteed to be stable as
2987
Item_direct_view_refs doesn't substitute itself with anything in
2988
Item_direct_view_ref::fix_fields.
2990
sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
2991
sj_nest->nested_join->sj_outer_expr_list.empty();
2993
if (subq_pred->left_expr->cols() == 1)
2995
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr);
2997
Item *item_eq= new Item_func_eq(subq_pred->left_expr,
2998
subq_lex->ref_pointer_array[0]);
2999
item_eq->name= (char*)subq_sj_cond_name;
3000
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3004
for (uint i= 0; i < subq_pred->left_expr->cols(); i++)
3006
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->
3009
new Item_func_eq(subq_pred->left_expr->element_index(i),
3010
subq_lex->ref_pointer_array[i]);
3011
item_eq->name= (char*)subq_sj_cond_name + (i % 64);
3012
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3015
/* Fix the created equality and AND */
3016
sj_nest->sj_on_expr->fix_fields(parent_join->thd, &sj_nest->sj_on_expr);
3019
Walk through sj nest's WHERE and ON expressions and call
3020
item->fix_table_changes() for all items.
3022
sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr);
3023
fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
3026
/* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
3027
subq_lex->master_unit()->exclude_level();
3029
/* Inject sj_on_expr into the parent's WHERE or ON */
3032
emb_tbl_nest->on_expr= and_items(emb_tbl_nest->on_expr,
3033
sj_nest->sj_on_expr);
3034
emb_tbl_nest->on_expr->fix_fields(parent_join->thd, &emb_tbl_nest->on_expr);
3038
/* Inject into the WHERE */
3039
parent_join->conds= and_items(parent_join->conds, sj_nest->sj_on_expr);
3040
parent_join->conds->fix_fields(parent_join->thd, &parent_join->conds);
3041
parent_join->select_lex->where= parent_join->conds;
3049
Convert candidate subquery predicates to semi-joins
3052
JOIN::flatten_subqueries()
3055
Convert candidate subquery predicates to semi-joins.
3062
bool JOIN::flatten_subqueries()
3064
Item_in_subselect **in_subq;
3065
Item_in_subselect **in_subq_end;
3067
if (sj_subselects.elements() == 0)
3070
/* 1. Fix children subqueries */
3071
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
3072
in_subq != in_subq_end; in_subq++)
3074
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3075
child_join->outer_tables = child_join->tables;
3076
if (child_join->flatten_subqueries())
3078
(*in_subq)->sj_convert_priority=
3079
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
3082
//dump_TABLE_LIST_struct(select_lex, select_lex->leaf_tables);
3084
2. Pick which subqueries to convert:
3085
sort the subquery array
3086
- prefer correlated subqueries over uncorrelated;
3087
- prefer subqueries that have greater number of outer tables;
3089
sj_subselects.sort(subq_sj_candidate_cmp);
3090
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
3091
/* Replace all subqueries to be flattened with Item_int(1) */
3092
for (in_subq= sj_subselects.front();
3093
in_subq != in_subq_end &&
3094
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3097
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
3101
for (in_subq= sj_subselects.front();
3102
in_subq != in_subq_end &&
3103
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3106
if (convert_subq_to_sj(this, *in_subq))
3110
/* 3. Finalize those we didn't convert */
3111
for (; in_subq!= in_subq_end; in_subq++)
3113
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3114
Item_subselect::trans_res res;
3115
(*in_subq)->changed= 0;
3116
(*in_subq)->fixed= 0;
3117
res= (*in_subq)->select_transformer(child_join);
3118
if (res == Item_subselect::RES_ERROR)
3121
(*in_subq)->changed= 1;
3122
(*in_subq)->fixed= 1;
3124
Item *substitute= (*in_subq)->substitution;
3125
bool do_fix_fields= !(*in_subq)->substitution->fixed;
3126
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
3129
//if ((*in_subq)->fix_fields(thd, (*in_subq)->ref_ptr))
3132
sj_subselects.clear();
3138
Setup for execution all subqueries of a query, for which the optimizer
3139
chose hash semi-join.
3141
@details Iterate over all subqueries of the query, and if they are under an
3142
IN predicate, and the optimizer chose to compute it via hash semi-join:
3143
- try to initialize all data structures needed for the materialized execution
3144
of the IN predicate,
3145
- if this fails, then perform the IN=>EXISTS transformation which was
3146
previously blocked during JOIN::prepare.
3148
This method is part of the "code generation" query processing phase.
3150
This phase must be called after substitute_for_best_equal_field() because
3151
that function may replace items with other items from a multiple equality,
3152
and we need to reference the correct items in the index access method of the
3155
@return Operation status
3156
@retval false success.
3157
@retval true error occurred.
3160
bool JOIN::setup_subquery_materialization()
3162
for (SELECT_LEX_UNIT *un= select_lex->first_inner_unit(); un;
3163
un= un->next_unit())
3165
for (SELECT_LEX *sl= un->first_select(); sl; sl= sl->next_select())
3167
Item_subselect *subquery_predicate= sl->master_unit()->item;
3168
if (subquery_predicate &&
3169
subquery_predicate->substype() == Item_subselect::IN_SUBS)
3171
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
3172
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
3173
in_subs->setup_engine())
3183
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3186
find_eq_ref_candidate()
3187
table Table to be checked
3188
sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
3192
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3195
Check again if it is feasible to factor common parts with constant table
3199
true - There exists an eq_ref(outer-tables) candidate
3203
bool find_eq_ref_candidate(TABLE *table, table_map sj_inner_tables)
3205
KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
3210
while (1) /* For each key */
3213
KEY *keyinfo= table->key_info + key;
3214
key_part_map bound_parts= 0;
3215
if ((keyinfo->flags & HA_NOSAME) == HA_NOSAME)
3217
do /* For all equalities on all key parts */
3219
/* Check if this is "t.keypart = expr(outer_tables) */
3220
if (!(keyuse->used_tables & sj_inner_tables) &&
3221
!(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
3223
bound_parts |= 1 << keyuse->keypart;
3226
} while (keyuse->key == key && keyuse->table == table);
3228
if (bound_parts == PREV_BITS(uint, keyinfo->key_parts))
3230
if (keyuse->table != table)
3238
if (keyuse->table != table)
3241
while (keyuse->key == key);
3250
Pull tables out of semi-join nests, if possible
3253
pull_out_semijoin_tables()
3254
join The join where to do the semi-join flattening
3257
Try to pull tables out of semi-join nests.
3260
When this function is called, the join may have several semi-join nests
3261
(possibly within different semi-join nests), but it is guaranteed that
3262
one semi-join nest does not contain another.
3265
A table can be pulled out of the semi-join nest if
3266
- It is a constant table
3270
* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer
3272
* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.
3273
* Semi-join nests TABLE_LIST::sj_inner_tables
3275
This operation is (and should be) performed at each PS execution since
3276
tables may become/cease to be constant across PS reexecutions.
3280
1 - Out of memory error
3283
int pull_out_semijoin_tables(JOIN *join)
3285
TABLE_LIST *sj_nest;
3286
List_iterator<TABLE_LIST> sj_list_it(join->select_lex->sj_nests);
3288
/* Try pulling out of the each of the semi-joins */
3289
while ((sj_nest= sj_list_it++))
3291
/* Action #1: Mark the constant tables to be pulled out */
3292
table_map pulled_tables= 0;
3294
List_iterator<TABLE_LIST> child_li(sj_nest->nested_join->join_list);
3296
while ((tbl= child_li++))
3300
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
3301
if (tbl->table->map & join->const_table_map)
3303
pulled_tables |= tbl->table->map;
3309
Action #2: Find which tables we can pull out based on
3310
update_ref_and_keys() data. Note that pulling one table out can allow
3311
us to pull out some other tables too.
3313
bool pulled_a_table;
3316
pulled_a_table= false;
3318
while ((tbl= child_li++))
3320
if (tbl->table && !(pulled_tables & tbl->table->map))
3322
if (find_eq_ref_candidate(tbl->table,
3323
sj_nest->nested_join->used_tables &
3326
pulled_a_table= true;
3327
pulled_tables |= tbl->table->map;
3331
} while (pulled_a_table);
3334
if ((sj_nest)->nested_join->used_tables == pulled_tables)
3336
(sj_nest)->sj_inner_tables= 0;
3337
while ((tbl= child_li++))
3340
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3345
/* Record the bitmap of inner tables, mark the inner tables */
3346
table_map inner_tables=(sj_nest)->nested_join->used_tables &
3348
(sj_nest)->sj_inner_tables= inner_tables;
3349
while ((tbl= child_li++))
3353
if (inner_tables & tbl->table->map)
3354
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
3356
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
473
3364
/*****************************************************************************
474
Create JoinTableS, make a guess about the table types,
3365
Create JOIN_TABS, make a guess about the table types,
475
3366
Approximate how many records will be used in each table
476
3367
*****************************************************************************/
477
ha_rows get_quick_record_count(Session *session, SQL_SELECT *select, Table *table, const key_map *keys,ha_rows limit)
3370
static ha_rows get_quick_record_count(THD *thd, SQL_SELECT *select,
3372
const key_map *keys,ha_rows limit)
480
if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))
3375
if (check_stack_overrun(thd, STACK_MIN_SIZE, NULL))
481
3376
return(0); // Fatal error flag is set
484
3379
select->head=table;
485
3380
table->reginfo.impossible_range=0;
486
if ((error= select->test_quick_select(session, *(key_map *)keys,(table_map) 0,
3381
if ((error= select->test_quick_select(thd, *(key_map *)keys,(table_map) 0,
487
3382
limit, 0, false)) == 1)
488
3383
return(select->quick->records);
489
3384
if (error == -1)
495
3390
return(HA_POS_ERROR); /* This shouldn't happend */
3394
This structure is used to collect info on potentially sargable
3395
predicates in order to check whether they become sargable after
3396
reading const tables.
3397
We form a bitmap of indexes that can be used for sargable predicates.
3398
Only such indexes are involved in range analysis.
3400
typedef struct st_sargable_param
3402
Field *field; /* field against which to check sargability */
3403
Item **arg_value; /* values of potential keys for lookups */
3404
uint num_values; /* number of values in the above array */
3408
Calculate the best possible join and initialize the join structure.
3417
make_join_statistics(JOIN *join, TABLE_LIST *tables, COND *conds,
3418
DYNAMIC_ARRAY *keyuse_array)
3422
uint i,table_count,const_count,key;
3423
table_map found_const_table_map, all_table_map, found_ref, refs;
3424
key_map const_ref, eq_part;
3425
TABLE **table_vector;
3426
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
3427
KEYUSE *keyuse,*start_keyuse;
3428
table_map outer_join=0;
3429
SARGABLE_PARAM *sargables= 0;
3430
JOIN_TAB *stat_vector[MAX_TABLES+1];
3432
table_count=join->tables;
3433
stat=(JOIN_TAB*) join->thd->calloc(sizeof(JOIN_TAB)*table_count);
3434
stat_ref=(JOIN_TAB**) join->thd->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
3435
table_vector=(TABLE**) join->thd->alloc(sizeof(TABLE*)*(table_count*2));
3436
if (!stat || !stat_ref || !table_vector)
3437
return(1); // Eom /* purecov: inspected */
3439
join->best_ref=stat_vector;
3441
stat_end=stat+table_count;
3442
found_const_table_map= all_table_map=0;
3447
s++, tables= tables->next_leaf, i++)
3449
TABLE_LIST *embedding= tables->embedding;
3452
s->const_keys.init();
3453
s->checked_keys.init();
3454
s->needed_reg.init();
3455
table_vector[i]=s->table=table=tables->table;
3456
table->pos_in_table_list= tables;
3457
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
3460
table->file->print_error(error, MYF(0));
3463
table->quick_keys.clear_all();
3464
table->reginfo.join_tab=s;
3465
table->reginfo.not_exists_optimize=0;
3466
memset(table->const_key_parts, 0,
3467
sizeof(key_part_map)*table->s->keys);
3468
all_table_map|= table->map;
3470
s->info=0; // For describe
3472
s->dependent= tables->dep_tables;
3473
s->key_dependent= 0;
3474
if (tables->schema_table)
3475
table->file->stats.records= 2;
3476
table->quick_condition_rows= table->file->stats.records;
3478
s->on_expr_ref= &tables->on_expr;
3479
if (*s->on_expr_ref)
3481
/* s is the only inner table of an outer join */
3482
if (!table->file->stats.records && !embedding)
3484
s->dependent= 0; // Ignore LEFT JOIN depend.
3485
set_position(join,const_count++,s,(KEYUSE*) 0);
3488
outer_join|= table->map;
3489
s->embedding_map= 0;
3490
for (;embedding; embedding= embedding->embedding)
3491
s->embedding_map|= embedding->nested_join->nj_map;
3494
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
3496
/* s belongs to a nested join, maybe to several embedded joins */
3497
s->embedding_map= 0;
3500
NESTED_JOIN *nested_join= embedding->nested_join;
3501
s->embedding_map|=nested_join->nj_map;
3502
s->dependent|= embedding->dep_tables;
3503
embedding= embedding->embedding;
3504
outer_join|= nested_join->used_tables;
3509
if ((table->file->stats.records <= 1) &&
3511
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && !join->no_const_tables)
3513
set_position(join,const_count++,s,(KEYUSE*) 0);
3517
join->outer_join=outer_join;
3519
if (join->outer_join)
3522
Build transitive closure for relation 'to be dependent on'.
3523
This will speed up the plan search for many cases with outer joins,
3524
as well as allow us to catch illegal cross references/
3525
Warshall's algorithm is used to build the transitive closure.
3526
As we use bitmaps to represent the relation the complexity
3527
of the algorithm is O((number of tables)^2).
3529
for (i= 0, s= stat ; i < table_count ; i++, s++)
3531
for (uint j= 0 ; j < table_count ; j++)
3533
table= stat[j].table;
3534
if (s->dependent & table->map)
3535
s->dependent |= table->reginfo.join_tab->dependent;
3538
s->table->maybe_null= 1;
3540
/* Catch illegal cross references for outer joins */
3541
for (i= 0, s= stat ; i < table_count ; i++, s++)
3543
if (s->dependent & s->table->map)
3545
join->tables=0; // Don't use join->table
3546
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
3549
s->key_dependent= s->dependent;
3553
if (conds || outer_join)
3554
if (update_ref_and_keys(join->thd, keyuse_array, stat, join->tables,
3555
conds, join->cond_equal,
3556
~outer_join, join->select_lex, &sargables))
3559
/* Read tables with 0 or 1 rows (system tables) */
3560
join->const_table_map= 0;
3562
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
3569
join->const_table_map|=s->table->map;
3570
if ((tmp=join_read_const_table(s, p_pos)))
3573
return(1); // Fatal error
3576
found_const_table_map|= s->table->map;
3579
/* loop until no more const tables are found */
3583
more_const_tables_found:
3588
We only have to loop from stat_vector + const_count as
3589
set_position() will move all const_tables first in stat_vector
3592
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
3597
If equi-join condition by a key is null rejecting and after a
3598
substitution of a const table the key value happens to be null
3599
then we can state that there are no matches for this equi-join.
3601
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
3604
When performing an outer join operation if there are no matching rows
3605
for the single row of the outer table all the inner tables are to be
3606
null complemented and thus considered as constant tables.
3607
Here we apply this consideration to the case of outer join operations
3608
with a single inner table only because the case with nested tables
3609
would require a more thorough analysis.
3610
TODO. Apply single row substitution to null complemented inner tables
3611
for nested outer join operations.
3613
while (keyuse->table == table)
3615
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
3616
keyuse->val->is_null() && keyuse->null_rejecting)
3619
mark_as_null_row(table);
3620
found_const_table_map|= table->map;
3621
join->const_table_map|= table->map;
3622
set_position(join,const_count++,s,(KEYUSE*) 0);
3623
goto more_const_tables_found;
3629
if (s->dependent) // If dependent on some table
3631
// All dep. must be constants
3632
if (s->dependent & ~(found_const_table_map))
3634
if (table->file->stats.records <= 1L &&
3635
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
3636
!table->pos_in_table_list->embedding)
3640
join->const_table_map|=table->map;
3641
set_position(join,const_count++,s,(KEYUSE*) 0);
3642
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
3645
return(1); // Fatal error
3648
found_const_table_map|= table->map;
3652
/* check if table can be read by key or table only uses const refs */
3653
if ((keyuse=s->keyuse))
3656
while (keyuse->table == table)
3658
start_keyuse=keyuse;
3660
s->keys.set_bit(key); // QQ: remove this ?
3663
const_ref.clear_all();
3664
eq_part.clear_all();
3667
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
3669
if (!((~found_const_table_map) & keyuse->used_tables))
3670
const_ref.set_bit(keyuse->keypart);
3672
refs|=keyuse->used_tables;
3673
eq_part.set_bit(keyuse->keypart);
3676
} while (keyuse->table == table && keyuse->key == key);
3678
if (eq_part.is_prefix(table->key_info[key].key_parts) &&
3679
!table->pos_in_table_list->embedding)
3681
if ((table->key_info[key].flags & (HA_NOSAME))
3684
if (const_ref == eq_part)
3685
{ // Found everything for ref.
3689
join->const_table_map|=table->map;
3690
set_position(join,const_count++,s,start_keyuse);
3691
if (create_ref_for_key(join, s, start_keyuse,
3692
found_const_table_map))
3694
if ((tmp=join_read_const_table(s,
3695
join->positions+const_count-1)))
3698
return(1); // Fatal error
3701
found_const_table_map|= table->map;
3705
found_ref|= refs; // Table is const if all refs are const
3707
else if (const_ref == eq_part)
3708
s->const_keys.set_bit(key);
3713
} while (join->const_table_map & found_ref && ref_changed);
3716
Update info on indexes that can be used for search lookups as
3717
reading const tables may has added new sargable predicates.
3719
if (const_count && sargables)
3721
for( ; sargables->field ; sargables++)
3723
Field *field= sargables->field;
3724
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
3725
key_map possible_keys= field->key_start;
3726
possible_keys.intersect(field->table->keys_in_use_for_query);
3728
for (uint j=0; j < sargables->num_values; j++)
3729
is_const&= sargables->arg_value[j]->const_item();
3731
join_tab[0].const_keys.merge(possible_keys);
3735
if (pull_out_semijoin_tables(join))
3738
/* Calc how many (possible) matched records in each table */
3740
for (s=stat ; s < stat_end ; s++)
3742
if (s->type == JT_SYSTEM || s->type == JT_CONST)
3744
/* Only one matching row */
3745
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
3748
/* Approximate found rows and time to read them */
3749
s->found_records=s->records=s->table->file->stats.records;
3750
s->read_time=(ha_rows) s->table->file->scan_time();
3753
Set a max range of how many seeks we can expect when using keys
3754
This is can't be to high as otherwise we are likely to use
3757
s->worst_seeks= min((double) s->found_records / 10,
3758
(double) s->read_time*3);
3759
if (s->worst_seeks < 2.0) // Fix for small tables
3763
Add to stat->const_keys those indexes for which all group fields or
3764
all select distinct fields participate in one index.
3766
add_group_and_distinct_keys(join, s);
3768
if (!s->const_keys.is_clear_all() &&
3769
!s->table->pos_in_table_list->embedding)
3773
select= make_select(s->table, found_const_table_map,
3774
found_const_table_map,
3775
*s->on_expr_ref ? *s->on_expr_ref : conds,
3779
records= get_quick_record_count(join->thd, select, s->table,
3780
&s->const_keys, join->row_limit);
3781
s->quick=select->quick;
3782
s->needed_reg=select->needed_reg;
3784
if (records == 0 && s->table->reginfo.impossible_range)
3787
Impossible WHERE or ON expression
3788
In case of ON, we mark that the we match one empty NULL row.
3789
In case of WHERE, don't set found_const_table_map to get the
3790
caller to abort with a zero row result.
3792
join->const_table_map|= s->table->map;
3793
set_position(join,const_count++,s,(KEYUSE*) 0);
3795
if (*s->on_expr_ref)
3797
/* Generate empty row */
3798
s->info= "Impossible ON condition";
3799
found_const_table_map|= s->table->map;
3801
mark_as_null_row(s->table); // All fields are NULL
3804
if (records != HA_POS_ERROR)
3806
s->found_records=records;
3807
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
3813
join->join_tab=stat;
3814
join->map2table=stat_ref;
3815
join->table= join->all_tables=table_vector;
3816
join->const_tables=const_count;
3817
join->found_const_table_map=found_const_table_map;
3819
/* Find an optimal join order of the non-constant tables. */
3820
if (join->const_tables != join->tables)
3822
optimize_keyuse(join, keyuse_array);
3823
if (choose_plan(join, all_table_map & ~join->const_table_map))
3828
memcpy(join->best_positions, join->positions,
3829
sizeof(POSITION)*join->const_tables);
3830
join->best_read=1.0;
3832
/* Generate an execution plan from the found optimal join order. */
3833
return(join->thd->killed || get_best_combination(join));
498
3837
/*****************************************************************************
499
3838
Check with keys are used and with tables references with tables
500
3839
Updates in stat:
503
3842
keyuse Pointer to possible keys
504
3843
*****************************************************************************/
3845
/// Used when finding key fields
3846
typedef struct key_field_t {
3848
Item *val; ///< May be empty if diff constant
3850
uint optimize; // KEY_OPTIMIZE_*
3853
If true, the condition this struct represents will not be satisfied
3856
bool null_rejecting;
3857
bool *cond_guard; /* See KEYUSE::cond_guard */
3858
uint sj_pred_no; /* See KEYUSE::sj_pred_no */
3862
Merge new key definitions to old ones, remove those not used in both.
3864
This is called for OR between different levels.
3866
To be able to do 'ref_or_null' we merge a comparison of a column
3867
and 'column IS NULL' to one test. This is useful for sub select queries
3868
that are internally transformed to something like:.
3871
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
3874
KEY_FIELD::null_rejecting is processed as follows: @n
3875
result has null_rejecting=true if it is set for both ORed references.
3877
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
3878
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
3881
The result of this is that we're missing some 'ref' accesses.
3882
OptimizerTeam: Fix this
3886
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
3889
if (start == new_fields)
3890
return start; // Impossible or
3891
if (new_fields == end)
3892
return start; // No new fields, skip all
3894
KEY_FIELD *first_free=new_fields;
3896
/* Mark all found fields in old array */
3897
for (; new_fields != end ; new_fields++)
3899
for (KEY_FIELD *old=start ; old != first_free ; old++)
3901
if (old->field == new_fields->field)
3904
NOTE: below const_item() call really works as "!used_tables()", i.e.
3905
it can return false where it is feasible to make it return true.
3907
The cause is as follows: Some of the tables are already known to be
3908
const tables (the detection code is in make_join_statistics(),
3909
above the update_ref_and_keys() call), but we didn't propagate
3910
information about this: TABLE::const_table is not set to true, and
3911
Item::update_used_tables() hasn't been called for each item.
3912
The result of this is that we're missing some 'ref' accesses.
3913
TODO: OptimizerTeam: Fix this
3915
if (!new_fields->val->const_item())
3918
If the value matches, we can use the key reference.
3919
If not, we keep it until we have examined all new values
3921
if (old->val->eq(new_fields->val, old->field->binary()))
3923
old->level= and_level;
3924
old->optimize= ((old->optimize & new_fields->optimize &
3925
KEY_OPTIMIZE_EXISTS) |
3926
((old->optimize | new_fields->optimize) &
3927
KEY_OPTIMIZE_REF_OR_NULL));
3928
old->null_rejecting= (old->null_rejecting &&
3929
new_fields->null_rejecting);
3932
else if (old->eq_func && new_fields->eq_func &&
3933
old->val->eq_by_collation(new_fields->val,
3934
old->field->binary(),
3935
old->field->charset()))
3938
old->level= and_level;
3939
old->optimize= ((old->optimize & new_fields->optimize &
3940
KEY_OPTIMIZE_EXISTS) |
3941
((old->optimize | new_fields->optimize) &
3942
KEY_OPTIMIZE_REF_OR_NULL));
3943
old->null_rejecting= (old->null_rejecting &&
3944
new_fields->null_rejecting);
3946
else if (old->eq_func && new_fields->eq_func &&
3947
((old->val->const_item() && old->val->is_null()) ||
3948
new_fields->val->is_null()))
3950
/* field = expression OR field IS NULL */
3951
old->level= and_level;
3952
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
3954
Remember the NOT NULL value unless the value does not depend
3957
if (!old->val->used_tables() && old->val->is_null())
3958
old->val= new_fields->val;
3959
/* The referred expression can be NULL: */
3960
old->null_rejecting= 0;
3965
We are comparing two different const. In this case we can't
3966
use a key-lookup on this so it's better to remove the value
3967
and let the range optimzier handle it
3969
if (old == --first_free) // If last item
3971
*old= *first_free; // Remove old value
3972
old--; // Retry this value
3977
/* Remove all not used items */
3978
for (KEY_FIELD *old=start ; old != first_free ;)
3980
if (old->level != and_level)
3981
{ // Not used in all levels
3982
if (old == --first_free)
3984
*old= *first_free; // Remove old value
3994
Add a possible key to array of possible keys if it's usable as a key
3996
@param key_fields Pointer to add key, if usable
3997
@param and_level And level, to be stored in KEY_FIELD
3998
@param cond Condition predicate
3999
@param field Field used in comparision
4000
@param eq_func True if we used =, <=> or IS NULL
4001
@param value Value used for comparison with field
4002
@param usable_tables Tables which can be used for key optimization
4003
@param sargables IN/OUT Array of found sargable candidates
4006
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
4007
table, we store this to be able to do not exists optimization later.
4010
*key_fields is incremented if we stored a key in the array
4014
add_key_field(KEY_FIELD **key_fields,uint and_level, Item_func *cond,
4015
Field *field, bool eq_func, Item **value, uint num_values,
4016
table_map usable_tables, SARGABLE_PARAM **sargables)
4018
uint exists_optimize= 0;
4019
if (!(field->flags & PART_KEY_FLAG))
4021
// Don't remove column IS NULL on a LEFT JOIN table
4022
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4023
!field->table->maybe_null || field->null_ptr)
4024
return; // Not a key. Skip it
4025
exists_optimize= KEY_OPTIMIZE_EXISTS;
4026
assert(num_values == 1);
4030
table_map used_tables=0;
4032
for (uint i=0; i<num_values; i++)
4034
used_tables|=(value[i])->used_tables();
4035
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
4040
if (!(usable_tables & field->table->map))
4042
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4043
!field->table->maybe_null || field->null_ptr)
4044
return; // Can't use left join optimize
4045
exists_optimize= KEY_OPTIMIZE_EXISTS;
4049
JOIN_TAB *stat=field->table->reginfo.join_tab;
4050
key_map possible_keys=field->key_start;
4051
possible_keys.intersect(field->table->keys_in_use_for_query);
4052
stat[0].keys.merge(possible_keys); // Add possible keys
4055
Save the following cases:
4057
Field LIKE constant where constant doesn't start with a wildcard
4058
Field = field2 where field2 is in a different table
4065
stat[0].key_dependent|=used_tables;
4068
for (uint i=0; i<num_values; i++)
4070
if (!(is_const&= value[i]->const_item()))
4074
stat[0].const_keys.merge(possible_keys);
4078
Save info to be able check whether this predicate can be
4079
considered as sargable for range analisis after reading const tables.
4080
We do not save info about equalities as update_const_equal_items
4081
will take care of updating info on keys from sargable equalities.
4084
(*sargables)->field= field;
4085
(*sargables)->arg_value= value;
4086
(*sargables)->num_values= num_values;
4089
We can't always use indexes when comparing a string index to a
4090
number. cmp_type() is checked to allow compare of dates to numbers.
4091
eq_func is NEVER true when num_values > 1
4096
Additional optimization: if we're processing
4097
"t.key BETWEEN c1 AND c1" then proceed as if we were processing
4099
TODO: This is a very limited fix. A more generic fix is possible.
4100
There are 2 options:
4101
A) Make equality propagation code be able to handle BETWEEN
4102
(including cases like t1.key BETWEEN t2.key AND t3.key)
4103
B) Make range optimizer to infer additional "t.key = c" equalities
4104
and use them in equality propagation process (see details in
4107
if ((cond->functype() != Item_func::BETWEEN) ||
4108
((Item_func_between*) cond)->negated ||
4109
!value[0]->eq(value[1], field->binary()))
4114
if (field->result_type() == STRING_RESULT)
4116
if ((*value)->result_type() != STRING_RESULT)
4118
if (field->cmp_type() != (*value)->result_type())
4124
We can't use indexes if the effective collation
4125
of the operation differ from the field collation.
4127
if (field->cmp_type() == STRING_RESULT &&
4128
((Field_str*)field)->charset() != cond->compare_collation())
4135
For the moment eq_func is always true. This slot is reserved for future
4136
extensions where we want to remembers other things than just eq comparisons
4139
/* Store possible eq field */
4140
(*key_fields)->field= field;
4141
(*key_fields)->eq_func= eq_func;
4142
(*key_fields)->val= *value;
4143
(*key_fields)->level= and_level;
4144
(*key_fields)->optimize= exists_optimize;
4146
If the condition has form "tbl.keypart = othertbl.field" and
4147
othertbl.field can be NULL, there will be no matches if othertbl.field
4149
We use null_rejecting in add_not_null_conds() to add
4150
'othertbl.field IS NOT NULL' to tab->select_cond.
4152
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
4153
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
4154
((*value)->type() == Item::FIELD_ITEM) &&
4155
((Item_field*)*value)->field->maybe_null());
4156
(*key_fields)->cond_guard= NULL;
4157
(*key_fields)->sj_pred_no= (cond->name >= subq_sj_cond_name &&
4158
cond->name < subq_sj_cond_name + 64)?
4159
cond->name - subq_sj_cond_name: UINT_MAX;
4164
Add possible keys to array of possible keys originated from a simple
4167
@param key_fields Pointer to add key, if usable
4168
@param and_level And level, to be stored in KEY_FIELD
4169
@param cond Condition predicate
4170
@param field Field used in comparision
4171
@param eq_func True if we used =, <=> or IS NULL
4172
@param value Value used for comparison with field
4173
Is NULL for BETWEEN and IN
4174
@param usable_tables Tables which can be used for key optimization
4175
@param sargables IN/OUT Array of found sargable candidates
4178
If field items f1 and f2 belong to the same multiple equality and
4179
a key is added for f1, the the same key is added for f2.
4182
*key_fields is incremented if we stored a key in the array
4186
add_key_equal_fields(KEY_FIELD **key_fields, uint and_level,
4187
Item_func *cond, Item_field *field_item,
4188
bool eq_func, Item **val,
4189
uint num_values, table_map usable_tables,
4190
SARGABLE_PARAM **sargables)
4192
Field *field= field_item->field;
4193
add_key_field(key_fields, and_level, cond, field,
4194
eq_func, val, num_values, usable_tables, sargables);
4195
Item_equal *item_equal= field_item->item_equal;
4199
Add to the set of possible key values every substitution of
4200
the field for an equal field included into item_equal
4202
Item_equal_iterator it(*item_equal);
4204
while ((item= it++))
4206
if (!field->eq(item->field))
4208
add_key_field(key_fields, and_level, cond, item->field,
4209
eq_func, val, num_values, usable_tables,
4217
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint *and_level,
4218
COND *cond, table_map usable_tables,
4219
SARGABLE_PARAM **sargables)
4221
if (cond->type() == Item_func::COND_ITEM)
4223
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
4224
KEY_FIELD *org_key_fields= *key_fields;
4226
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
4230
add_key_fields(join, key_fields, and_level, item, usable_tables,
4232
for (; org_key_fields != *key_fields ; org_key_fields++)
4233
org_key_fields->level= *and_level;
4238
add_key_fields(join, key_fields, and_level, li++, usable_tables,
4243
KEY_FIELD *start_key_fields= *key_fields;
4245
add_key_fields(join, key_fields, and_level, item, usable_tables,
4247
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
4248
*key_fields,++(*and_level));
4255
Subquery optimization: Conditions that are pushed down into subqueries
4256
are wrapped into Item_func_trig_cond. We process the wrapped condition
4257
but need to set cond_guard for KEYUSE elements generated from it.
4260
if (cond->type() == Item::FUNC_ITEM &&
4261
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
4263
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
4264
if (!join->group_list && !join->order &&
4266
join->unit->item->substype() == Item_subselect::IN_SUBS &&
4267
!join->unit->is_union())
4269
KEY_FIELD *save= *key_fields;
4270
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
4272
// Indicate that this ref access candidate is for subquery lookup:
4273
for (; save != *key_fields; save++)
4274
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
4280
/* If item is of type 'field op field/constant' add it to key_fields */
4281
if (cond->type() != Item::FUNC_ITEM)
4283
Item_func *cond_func= (Item_func*) cond;
4284
switch (cond_func->select_optimize()) {
4285
case Item_func::OPTIMIZE_NONE:
4287
case Item_func::OPTIMIZE_KEY:
4291
if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
4292
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4294
values= cond_func->arguments()+1;
4295
if (cond_func->functype() == Item_func::NE_FUNC &&
4296
cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4297
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4299
assert(cond_func->functype() != Item_func::IN_FUNC ||
4300
cond_func->argument_count() != 2);
4301
add_key_equal_fields(key_fields, *and_level, cond_func,
4302
(Item_field*) (cond_func->key_item()->real_item()),
4304
cond_func->argument_count()-1,
4305
usable_tables, sargables);
4307
if (cond_func->functype() == Item_func::BETWEEN)
4309
values= cond_func->arguments();
4310
for (uint i= 1 ; i < cond_func->argument_count() ; i++)
4312
Item_field *field_item;
4313
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
4315
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
4317
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
4318
add_key_equal_fields(key_fields, *and_level, cond_func,
4319
field_item, 0, values, 1, usable_tables,
4326
case Item_func::OPTIMIZE_OP:
4328
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
4329
cond_func->functype() == Item_func::EQUAL_FUNC);
4331
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4332
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4334
add_key_equal_fields(key_fields, *and_level, cond_func,
4335
(Item_field*) (cond_func->arguments()[0])->real_item(),
4337
cond_func->arguments()+1, 1, usable_tables,
4340
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4341
cond_func->functype() != Item_func::LIKE_FUNC &&
4342
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
4344
add_key_equal_fields(key_fields, *and_level, cond_func,
4345
(Item_field*) (cond_func->arguments()[1])->real_item(),
4347
cond_func->arguments(),1,usable_tables,
4352
case Item_func::OPTIMIZE_NULL:
4353
/* column_name IS [NOT] NULL */
4354
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4355
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4357
Item *tmp=new Item_null;
4358
if (unlikely(!tmp)) // Should never be true
4360
add_key_equal_fields(key_fields, *and_level, cond_func,
4361
(Item_field*) (cond_func->arguments()[0])->real_item(),
4362
cond_func->functype() == Item_func::ISNULL_FUNC,
4363
&tmp, 1, usable_tables, sargables);
4366
case Item_func::OPTIMIZE_EQUAL:
4367
Item_equal *item_equal= (Item_equal *) cond;
4368
Item *const_item= item_equal->get_const();
4369
Item_equal_iterator it(*item_equal);
4374
For each field field1 from item_equal consider the equality
4375
field1=const_item as a condition allowing an index access of the table
4376
with field1 by the keys value of field1.
4378
while ((item= it++))
4380
add_key_field(key_fields, *and_level, cond_func, item->field,
4381
true, &const_item, 1, usable_tables, sargables);
4387
Consider all pairs of different fields included into item_equal.
4388
For each of them (field1, field1) consider the equality
4389
field1=field2 as a condition allowing an index access of the table
4390
with field1 by the keys value of field2.
4392
Item_equal_iterator fi(*item_equal);
4393
while ((item= fi++))
4395
Field *field= item->field;
4396
while ((item= it++))
4398
if (!field->eq(item->field))
4400
add_key_field(key_fields, *and_level, cond_func, field,
4401
true, (Item **) &item, 1, usable_tables,
508
4413
Add all keys with uses 'field' for some keypart.
510
4415
If field->and_level != and_level then only mark key_part as const_part.
512
uint32_t max_part_bit(key_part_map bits)
4419
max_part_bit(key_part_map bits)
515
4422
for (found=0; bits & 1 ; found++,bits>>=1) ;
519
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)
4427
add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
4429
Field *field=key_field->field;
4430
TABLE *form= field->table;
4433
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
4435
for (uint key= 0 ; key < form->sizeKeys() ; key++)
4437
if (!(form->keys_in_use_for_query.is_set(key)))
4440
uint key_parts= (uint) form->key_info[key].key_parts;
4441
for (uint part=0 ; part < key_parts ; part++)
4443
if (field->eq(form->key_info[key].key_part[part].field))
4445
keyuse.table= field->table;
4446
keyuse.val = key_field->val;
4448
keyuse.keypart=part;
4449
keyuse.keypart_map= (key_part_map) 1 << part;
4450
keyuse.used_tables=key_field->val->used_tables();
4451
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
4452
keyuse.null_rejecting= key_field->null_rejecting;
4453
keyuse.cond_guard= key_field->cond_guard;
4454
keyuse.sj_pred_no= key_field->sj_pred_no;
4455
VOID(insert_dynamic(keyuse_array,(uchar*) &keyuse));
4463
sort_keyuse(KEYUSE *a,KEYUSE *b)
522
if (a->getTable()->tablenr != b->getTable()->tablenr)
523
return static_cast<int>((a->getTable()->tablenr - b->getTable()->tablenr));
524
if (a->getKey() != b->getKey())
525
return static_cast<int>((a->getKey() - b->getKey()));
526
if (a->getKeypart() != b->getKeypart())
527
return static_cast<int>((a->getKeypart() - b->getKeypart()));
4466
if (a->table->tablenr != b->table->tablenr)
4467
return (int) (a->table->tablenr - b->table->tablenr);
4468
if (a->key != b->key)
4469
return (int) (a->key - b->key);
4470
if (a->keypart != b->keypart)
4471
return (int) (a->keypart - b->keypart);
528
4472
// Place const values before other ones
529
if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -
530
test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))
4473
if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
4474
test((b->used_tables & ~OUTER_REF_TABLE_BIT))))
532
4476
/* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
533
return static_cast<int>(((a->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) -
534
(b->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)));
4477
return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
4478
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
4483
Add to KEY_FIELD array all 'ref' access candidates within nested join.
4485
This function populates KEY_FIELD array with entries generated from the
4486
ON condition of the given nested join, and does the same for nested joins
4487
contained within this nested join.
4489
@param[in] nested_join_table Nested join pseudo-table to process
4490
@param[in,out] end End of the key field array
4491
@param[in,out] and_level And-level
4492
@param[in,out] sargables Array of found sargable candidates
4496
We can add accesses to the tables that are direct children of this nested
4497
join (1), and are not inner tables w.r.t their neighbours (2).
4499
Example for #1 (outer brackets pair denotes nested join this function is
4502
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
4506
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
4508
In examples 1-2 for condition cond, we can add 'ref' access candidates to
4512
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
4514
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
4517
static void add_key_fields_for_nj(JOIN *join, TABLE_LIST *nested_join_table,
4518
KEY_FIELD **end, uint *and_level,
4519
SARGABLE_PARAM **sargables)
4521
List_iterator<TABLE_LIST> li(nested_join_table->nested_join->join_list);
4522
List_iterator<TABLE_LIST> li2(nested_join_table->nested_join->join_list);
4523
bool have_another = false;
4524
table_map tables= 0;
4526
assert(nested_join_table->nested_join);
4528
while ((table= li++) || (have_another && (li=li2, have_another=false,
4531
if (table->nested_join)
4533
if (!table->on_expr)
4535
/* It's a semi-join nest. Walk into it as if it wasn't a nest */
4538
li= List_iterator<TABLE_LIST>(table->nested_join->join_list);
4541
add_key_fields_for_nj(join, table, end, and_level, sargables);
4544
if (!table->on_expr)
4545
tables |= table->table->map;
4547
if (nested_join_table->on_expr)
4548
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
539
4554
Update keyuse array with all possible keys we can use to fetch rows.
542
@param[out] keyuse Put here ordered array of KeyUse structures
4557
@param[out] keyuse Put here ordered array of KEYUSE structures
543
4558
@param join_tab Array in tablenr_order
544
4559
@param tables Number of tables in join
545
4560
@param cond WHERE condition (note that the function analyzes
790
4813
/* Intersect the keys of all group fields. */
791
4814
cur_item= indexed_fields_it++;
792
possible_keys|= cur_item->field->part_of_key;
4815
possible_keys.merge(cur_item->field->part_of_key);
793
4816
while ((cur_item= indexed_fields_it++))
795
possible_keys&= cur_item->field->part_of_key;
798
if (possible_keys.any())
799
join_tab->const_keys|= possible_keys;
803
Compare two JoinTable objects based on the number of accessed records.
805
@param ptr1 pointer to first JoinTable object
806
@param ptr2 pointer to second JoinTable object
4818
possible_keys.intersect(cur_item->field->part_of_key);
4821
if (!possible_keys.is_clear_all())
4822
join_tab->const_keys.merge(possible_keys);
4826
/*****************************************************************************
4827
Go through all combinations of not marked tables and find the one
4828
which uses least records
4829
*****************************************************************************/
4831
/** Save const tables first as used tables. */
4834
set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key)
4836
join->positions[idx].table= table;
4837
join->positions[idx].key=key;
4838
join->positions[idx].records_read=1.0; /* This is a const table */
4839
join->positions[idx].ref_depend_map= 0;
4841
/* Move the const table as down as possible in best_ref */
4842
JOIN_TAB **pos=join->best_ref+idx+1;
4843
JOIN_TAB *next=join->best_ref[idx];
4844
for (;next != table ; pos++)
4846
JOIN_TAB *tmp=pos[0];
4850
join->best_ref[idx]=table;
4855
Given a semi-join nest, find out which of the IN-equalities are bound
4858
get_bound_sj_equalities()
4859
sj_nest Semi-join nest
4860
remaining_tables Tables that are not yet bound
4863
Given a semi-join nest, find out which of the IN-equalities have their
4864
left part expression bound (i.e. the said expression doesn't refer to
4865
any of remaining_tables and can be evaluated).
4868
Bitmap of bound IN-equalities.
4871
uint64_t get_bound_sj_equalities(TABLE_LIST *sj_nest,
4872
table_map remaining_tables)
4874
List_iterator<Item> li(sj_nest->nested_join->sj_outer_expr_list);
4878
while ((item= li++))
4881
Q: should this take into account equality propagation and how?
4882
A: If e->outer_side is an Item_field, walk over the equality
4883
class and see if there is an element that is bound?
4884
(this is an optional feature)
4886
if (!(item->used_tables() & remaining_tables))
4896
Find the best access path for an extension of a partial execution
4897
plan and add this path to the plan.
4899
The function finds the best access path to table 's' from the passed
4900
partial plan where an access path is the general term for any means to
4901
access the data in 's'. An access path may use either an index or a scan,
4902
whichever is cheaper. The input partial plan is passed via the array
4903
'join->positions' of length 'idx'. The chosen access method for 's' and its
4904
cost are stored in 'join->positions[idx]'.
4906
@param join pointer to the structure providing all context info
4908
@param s the table to be joined by the function
4909
@param thd thread for the connection that submitted the query
4910
@param remaining_tables set of tables not included into the partial plan yet
4911
@param idx the length of the partial plan
4912
@param record_count estimate for the number of records returned by the
4914
@param read_time the cost of the partial plan
4921
best_access_path(JOIN *join,
4924
table_map remaining_tables,
4926
double record_count,
4927
double read_time __attribute__((unused)))
4929
KEYUSE *best_key= 0;
4930
uint best_max_key_part= 0;
4931
bool found_constraint= 0;
4932
double best= DBL_MAX;
4933
double best_time= DBL_MAX;
4934
double records= DBL_MAX;
4935
table_map best_ref_depends_map= 0;
4938
uint best_is_sj_inside_out= 0;
4941
{ /* Use key if possible */
4942
TABLE *table= s->table;
4943
KEYUSE *keyuse,*start_key=0;
4944
double best_records= DBL_MAX;
4945
uint max_key_part=0;
4946
uint64_t bound_sj_equalities= 0;
4947
bool try_sj_inside_out= false;
4949
Discover the bound equalites. We need to do this, if
4950
1. The next table is an SJ-inner table, and
4951
2. It is the first table from that semijoin, and
4952
3. We're not within a semi-join range (i.e. all semi-joins either have
4953
all or none of their tables in join_table_map), except
4954
s->emb_sj_nest (which we've just entered).
4955
3. All correlation references from this sj-nest are bound
4957
if (s->emb_sj_nest && // (1)
4958
s->emb_sj_nest->sj_in_exprs < 64 &&
4959
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
4960
s->emb_sj_nest->sj_inner_tables) && // (2)
4961
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
4962
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
4964
/* This table is an InsideOut scan candidate */
4965
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
4967
try_sj_inside_out= true;
4970
/* Test how we can use keys */
4971
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
4972
for (keyuse=s->keyuse ; keyuse->table == table ;)
4974
key_part_map found_part= 0;
4975
table_map found_ref= 0;
4976
uint key= keyuse->key;
4977
KEY *keyinfo= table->key_info+key;
4978
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
4979
key_part_map const_part= 0;
4980
/* The or-null keypart in ref-or-null access: */
4981
key_part_map ref_or_null_part= 0;
4983
/* Calculate how many key segments of the current key we can use */
4985
uint64_t handled_sj_equalities=0;
4986
key_part_map sj_insideout_map= 0;
4988
do /* For each keypart */
4990
uint keypart= keyuse->keypart;
4991
table_map best_part_found_ref= 0;
4992
double best_prev_record_reads= DBL_MAX;
4994
do /* For each way to access the keypart */
4998
if 1. expression doesn't refer to forward tables
4999
2. we won't get two ref-or-null's
5001
if (!(remaining_tables & keyuse->used_tables) &&
5002
!(ref_or_null_part && (keyuse->optimize &
5003
KEY_OPTIMIZE_REF_OR_NULL)))
5005
found_part|= keyuse->keypart_map;
5006
if (!(keyuse->used_tables & ~join->const_table_map))
5007
const_part|= keyuse->keypart_map;
5009
double tmp2= prev_record_reads(join, idx, (found_ref |
5010
keyuse->used_tables));
5011
if (tmp2 < best_prev_record_reads)
5013
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
5014
best_prev_record_reads= tmp2;
5016
if (rec > keyuse->ref_table_rows)
5017
rec= keyuse->ref_table_rows;
5019
If there is one 'key_column IS NULL' expression, we can
5020
use this ref_or_null optimisation of this field
5022
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
5023
ref_or_null_part |= keyuse->keypart_map;
5026
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
5028
if (!(remaining_tables & keyuse->used_tables))
5029
bound_sj_equalities |= 1ULL << keyuse->sj_pred_no;
5032
handled_sj_equalities |= 1ULL << keyuse->sj_pred_no;
5033
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
5038
} while (keyuse->table == table && keyuse->key == key &&
5039
keyuse->keypart == keypart);
5040
found_ref|= best_part_found_ref;
5041
} while (keyuse->table == table && keyuse->key == key);
5044
Assume that that each key matches a proportional part of table.
5046
if (!found_part && !handled_sj_equalities)
5047
continue; // Nothing usable found
5049
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
5050
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
5052
bool sj_inside_out_scan= false;
5054
found_constraint= 1;
5056
Check if InsideOut scan is applicable:
5057
1. All IN-equalities are either "bound" or "handled"
5058
2. Index keyparts are
5061
if (try_sj_inside_out &&
5062
table->covering_keys.is_set(key) &&
5063
(handled_sj_equalities | bound_sj_equalities) == // (1)
5064
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
5066
uint n_fixed_parts= max_part_bit(found_part);
5067
if (n_fixed_parts != keyinfo->key_parts &&
5068
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
5069
PREV_BITS(uint, keyinfo->key_parts))
5072
Not all parts are fixed. Produce bitmap of remaining bits and
5073
check if all of them are covered.
5075
sj_inside_out_scan= true;
5079
It's a confluent ref scan.
5081
That is, all found KEYUSE elements refer to IN-equalities,
5082
and there is really no ref access because there is no
5083
t.keypart0 = {bound expression}
5085
Calculate the cost of complete loose index scan.
5087
records= (double)s->table->file->stats.records;
5089
/* The cost is entire index scan cost (divided by 2) */
5090
best_time= s->table->file->index_only_read_time(key, records);
5092
/* Now figure how many different keys we will get */
5094
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
5095
records= records / rpc;
5102
Check if we found full key
5104
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
5107
max_key_part= (uint) ~0;
5108
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
5110
tmp = prev_record_reads(join, idx, found_ref);
5116
{ /* We found a const key */
5118
ReuseRangeEstimateForRef-1:
5119
We get here if we've found a ref(const) (c_i are constants):
5120
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
5122
If range optimizer was able to construct a "range"
5123
access on this index, then its condition "quick_cond" was
5124
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
5125
from the range optimizer.
5127
Proof of (*): By properties of range and ref optimizers
5128
quick_cond will be equal or tighther than ref_const_cond.
5129
ref_const_cond already covers "smallest" possible interval -
5130
a singlepoint interval over all keyparts. Therefore,
5131
quick_cond is equivalent to ref_const_cond (if it was an
5132
empty interval we wouldn't have got here).
5134
if (table->quick_keys.is_set(key))
5135
records= (double) table->quick_rows[key];
5138
/* quick_range couldn't use key! */
5139
records= (double) s->records/rec;
5144
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
5145
{ /* Prefer longer keys */
5147
((double) s->records / (double) rec *
5149
((double) (table->s->max_key_length-keyinfo->key_length) /
5150
(double) table->s->max_key_length)));
5152
records=2.0; /* Can't be as good as a unique */
5155
ReuseRangeEstimateForRef-2: We get here if we could not reuse
5156
E(#rows) from range optimizer. Make another try:
5158
If range optimizer produced E(#rows) for a prefix of the ref
5159
access we're considering, and that E(#rows) is lower then our
5160
current estimate, make an adjustment. The criteria of when we
5161
can make an adjustment is a special case of the criteria used
5162
in ReuseRangeEstimateForRef-3.
5164
if (table->quick_keys.is_set(key) &&
5165
const_part & (1 << table->quick_key_parts[key]) &&
5166
table->quick_n_ranges[key] == 1 &&
5167
records > (double) table->quick_rows[key])
5169
records= (double) table->quick_rows[key];
5172
/* Limit the number of matched rows */
5174
set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key);
5175
if (table->covering_keys.is_set(key))
5177
/* we can use only index tree */
5178
tmp= record_count * table->file->index_only_read_time(key, tmp);
5181
tmp= record_count*min(tmp,s->worst_seeks);
5187
Use as much key-parts as possible and a uniq key is better
5188
than a not unique key
5189
Set tmp to (previous record count) * (records / combination)
5191
if ((found_part & 1) &&
5192
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
5193
found_part == PREV_BITS(uint,keyinfo->key_parts)))
5195
max_key_part= max_part_bit(found_part);
5197
ReuseRangeEstimateForRef-3:
5198
We're now considering a ref[or_null] access via
5199
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
5200
(same-as-above but with one cond replaced
5201
with "t.keypart_i IS NULL")] (**)
5203
Try re-using E(#rows) from "range" optimizer:
5204
We can do so if "range" optimizer used the same intervals as
5205
in (**). The intervals used by range optimizer may be not
5206
available at this point (as "range" access might have choosen to
5207
create quick select over another index), so we can't compare
5208
them to (**). We'll make indirect judgements instead.
5209
The sufficient conditions for re-use are:
5210
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
5211
this is not satisfied we have no way to know which ranges
5212
will be actually scanned by 'ref' until we execute the
5214
(C2) max #key parts in 'range' access == K == max_key_part (this
5215
is apparently a necessary requirement)
5217
We also have a property that "range optimizer produces equal or
5218
tighter set of scan intervals than ref(const) optimizer". Each
5219
of the intervals in (**) are "tightest possible" intervals when
5220
one limits itself to using keyparts 1..K (which we do in #2).
5221
From here it follows that range access used either one, or
5222
both of the (I1) and (I2) intervals:
5224
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
5225
(same-as-above but with one cond replaced
5226
with "t.keypart_i IS NULL") (I2)
5228
The remaining part is to exclude the situation where range
5229
optimizer used one interval while we're considering
5230
ref-or-null and looking for estimate for two intervals. This
5231
is done by last limitation:
5233
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
5235
if (table->quick_keys.is_set(key) && !found_ref && //(C1)
5236
table->quick_key_parts[key] == max_key_part && //(C2)
5237
table->quick_n_ranges[key] == 1+test(ref_or_null_part)) //(C3)
5239
tmp= records= (double) table->quick_rows[key];
5243
/* Check if we have statistic about the distribution */
5244
if ((records= keyinfo->rec_per_key[max_key_part-1]))
5247
Fix for the case where the index statistics is too
5249
(1) We're considering ref(const) and there is quick select
5251
(2) and that quick select uses more keyparts (i.e. it will
5252
scan equal/smaller interval then this ref(const))
5253
(3) and E(#rows) for quick select is higher then our
5256
We'll use E(#rows) from quick select.
5258
Q: Why do we choose to use 'ref'? Won't quick select be
5259
cheaper in some cases ?
5260
TODO: figure this out and adjust the plan choice if needed.
5262
if (!found_ref && table->quick_keys.is_set(key) && // (1)
5263
table->quick_key_parts[key] > max_key_part && // (2)
5264
records < (double)table->quick_rows[key]) // (3)
5265
records= (double)table->quick_rows[key];
5272
Assume that the first key part matches 1% of the file
5273
and that the whole key matches 10 (duplicates) or 1
5275
Assume also that more key matches proportionally more
5277
This gives the formula:
5278
records = (x * (b-a) + a*c-b)/(c-1)
5280
b = records matched by whole key
5281
a = records matched by first key part (1% of all records?)
5282
c = number of key parts in key
5283
x = used key parts (1 <= x <= c)
5286
if (!(rec_per_key=(double)
5287
keyinfo->rec_per_key[keyinfo->key_parts-1]))
5288
rec_per_key=(double) s->records/rec+1;
5292
else if (rec_per_key/(double) s->records >= 0.01)
5296
double a=s->records*0.01;
5297
if (keyinfo->key_parts > 1)
5298
tmp= (max_key_part * (rec_per_key - a) +
5299
a*keyinfo->key_parts - rec_per_key)/
5300
(keyinfo->key_parts-1);
5303
set_if_bigger(tmp,1.0);
5305
records = (ulong) tmp;
5308
if (ref_or_null_part)
5310
/* We need to do two key searches to find key */
5316
ReuseRangeEstimateForRef-4: We get here if we could not reuse
5317
E(#rows) from range optimizer. Make another try:
5319
If range optimizer produced E(#rows) for a prefix of the ref
5320
access we're considering, and that E(#rows) is lower then our
5321
current estimate, make the adjustment.
5323
The decision whether we can re-use the estimate from the range
5324
optimizer is the same as in ReuseRangeEstimateForRef-3,
5325
applied to first table->quick_key_parts[key] key parts.
5327
if (table->quick_keys.is_set(key) &&
5328
table->quick_key_parts[key] <= max_key_part &&
5329
const_part & (1 << table->quick_key_parts[key]) &&
5330
table->quick_n_ranges[key] == 1 + test(ref_or_null_part &
5332
records > (double) table->quick_rows[key])
5334
tmp= records= (double) table->quick_rows[key];
5338
/* Limit the number of matched rows */
5339
set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key);
5340
if (table->covering_keys.is_set(key))
5342
/* we can use only index tree */
5343
tmp= record_count * table->file->index_only_read_time(key, tmp);
5346
tmp= record_count * min(tmp,s->worst_seeks);
5349
tmp= best_time; // Do nothing
5352
if (sj_inside_out_scan && !start_key)
5360
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
5362
best_time= tmp + records/(double) TIME_FOR_COMPARE;
5364
best_records= records;
5365
best_key= start_key;
5366
best_max_key_part= max_key_part;
5367
best_ref_depends_map= found_ref;
5368
best_is_sj_inside_out= sj_inside_out_scan;
5371
records= best_records;
5375
Don't test table scan if it can't be better.
5376
Prefer key lookup if we would use the same key for scanning.
5378
Don't do a table scan on InnoDB tables, if we can read the used
5379
parts of the row from any of the used index.
5380
This is because table scans uses index and we would not win
5381
anything by using a table scan.
5383
A word for word translation of the below if-statement in sergefp's
5384
understanding: we check if we should use table scan if:
5385
(1) The found 'ref' access produces more records than a table scan
5386
(or index scan, or quick select), or 'ref' is more expensive than
5388
(2) This doesn't hold: the best way to perform table scan is to to perform
5389
'range' access using index IDX, and the best way to perform 'ref'
5390
access is to use the same index IDX, with the same or more key parts.
5391
(note: it is not clear how this rule is/should be extended to
5392
index_merge quick selects)
5393
(3) See above note about InnoDB.
5394
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
5395
path, but there is no quick select)
5396
If the condition in the above brackets holds, then the only possible
5397
"table scan" access method is ALL/index (there is no quick select).
5398
Since we have a 'ref' access path, and FORCE INDEX instructs us to
5399
choose it over ALL/index, there is no need to consider a full table
5402
if ((records >= s->found_records || best > s->read_time) && // (1)
5403
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
5404
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
5405
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
5406
! s->table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
5407
!(s->table->force_index && best_key && !s->quick)) // (4)
5408
{ // Check full join
5409
ha_rows rnd_records= s->found_records;
5411
If there is a filtering condition on the table (i.e. ref analyzer found
5412
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
5413
preceding this table in the join order we're now considering), then
5414
assume that 25% of the rows will be filtered out by this condition.
5416
This heuristic is supposed to force tables used in exprZ to be before
5417
this table in join order.
5419
if (found_constraint)
5420
rnd_records-= rnd_records/4;
5423
If applicable, get a more accurate estimate. Don't use the two
5426
if (s->table->quick_condition_rows != s->found_records)
5427
rnd_records= s->table->quick_condition_rows;
5430
Range optimizer never proposes a RANGE if it isn't better
5431
than FULL: so if RANGE is present, it's always preferred to FULL.
5432
Here we estimate its cost.
5438
- read record range through 'quick'
5439
- skip rows which does not satisfy WHERE constraints
5441
We take into account possible use of join cache for ALL/index
5442
access (see first else-branch below), but we don't take it into
5443
account here for range/index_merge access. Find out why this is so.
5446
(s->quick->read_time +
5447
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
5451
/* Estimate cost of reading table. */
5452
tmp= s->table->file->scan_time();
5453
if (s->table->map & join->outer_join) // Can't use join cache
5456
For each record we have to:
5457
- read the whole table record
5458
- skip rows which does not satisfy join condition
5462
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
5466
/* We read the table as many times as join buffer becomes full. */
5467
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
5469
(double) thd->variables.join_buff_size));
5471
We don't make full cartesian product between rows in the scanned
5472
table and existing records because we skip all rows from the
5473
scanned table, which does not satisfy join condition when
5474
we read the table (see flush_cached_records for details). Here we
5475
take into account cost to read and skip these records.
5477
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
5482
We estimate the cost of evaluating WHERE clause for found records
5483
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
5484
tmp give us total cost of using TABLE SCAN
5486
if (best == DBL_MAX ||
5487
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
5488
best + record_count/(double) TIME_FOR_COMPARE*records))
5491
If the table has a range (s->quick is set) make_join_select()
5492
will ensure that this will be used
5495
records= rows2double(rnd_records);
5497
/* range/index_merge/ALL/index access method are "independent", so: */
5498
best_ref_depends_map= 0;
5499
best_is_sj_inside_out= false;
5503
/* Update the cost information for the current partial plan */
5504
join->positions[idx].records_read= records;
5505
join->positions[idx].read_time= best;
5506
join->positions[idx].key= best_key;
5507
join->positions[idx].table= s;
5508
join->positions[idx].ref_depend_map= best_ref_depends_map;
5509
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
5512
idx == join->const_tables &&
5513
s->table == join->sort_by_table &&
5514
join->unit->select_limit_cnt >= records)
5515
join->sort_by_table= (TABLE*) 1; // Must use temporary table
5522
Selects and invokes a search strategy for an optimal query plan.
5524
The function checks user-configurable parameters that control the search
5525
strategy for an optimal plan, selects the search method and then invokes
5526
it. Each specific optimization procedure stores the final optimal plan in
5527
the array 'join->best_positions', and the cost of the plan in
5530
@param join pointer to the structure providing all context info for
5532
@param join_tables set of the tables in the query
5535
'MAX_TABLES+2' denotes the old implementation of find_best before
5536
the greedy version. Will be removed when greedy_search is approved.
5545
choose_plan(JOIN *join, table_map join_tables)
5547
uint search_depth= join->thd->variables.optimizer_search_depth;
5548
uint prune_level= join->thd->variables.optimizer_prune_level;
5549
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
5551
join->cur_embedding_map= 0;
5552
reset_nj_counters(join->join_list);
5554
if (SELECT_STRAIGHT_JOIN option is set)
5555
reorder tables so dependent tables come after tables they depend
5556
on, otherwise keep tables in the order they were specified in the query
5558
Apply heuristic: pre-sort all access plans with respect to the number of
5561
my_qsort(join->best_ref + join->const_tables,
5562
join->tables - join->const_tables, sizeof(JOIN_TAB*),
5563
straight_join ? join_tab_cmp_straight : join_tab_cmp);
5564
join->cur_emb_sj_nests= 0;
5567
optimize_straight_join(join, join_tables);
5571
if (search_depth == MAX_TABLES+2)
5573
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
5574
the greedy version. Will be removed when greedy_search is approved.
5576
join->best_read= DBL_MAX;
5577
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
5582
if (search_depth == 0)
5583
/* Automatically determine a reasonable value for 'search_depth' */
5584
search_depth= determine_search_depth(join);
5585
if (greedy_search(join, join_tables, search_depth, prune_level))
5591
Store the cost of this query into a user variable
5592
Don't update last_query_cost for statements that are not "flat joins" :
5593
i.e. they have subqueries, unions or call stored procedures.
5594
TODO: calculate a correct cost for a query with subqueries and UNIONs.
5596
if (join->thd->lex->is_single_level_stmt())
5597
join->thd->status_var.last_query_cost= join->best_read;
5603
Compare two JOIN_TAB objects based on the number of accessed records.
5605
@param ptr1 pointer to first JOIN_TAB object
5606
@param ptr2 pointer to second JOIN_TAB object
809
5609
The order relation implemented by join_tab_cmp() is not transitive,
5663
Heuristic procedure to automatically guess a reasonable degree of
5664
exhaustiveness for the greedy search procedure.
5666
The procedure estimates the optimization time and selects a search depth
5667
big enough to result in a near-optimal QEP, that doesn't take too long to
5668
find. If the number of tables in the query exceeds some constant, then
5669
search_depth is set to this constant.
5671
@param join pointer to the structure providing all context info for
5675
This is an extremely simplistic implementation that serves as a stub for a
5676
more advanced analysis of the join. Ideally the search depth should be
5677
determined by learning from previous query optimizations, because it will
5678
depend on the CPU power (and other factors).
5681
this value should be determined dynamically, based on statistics:
5682
uint max_tables_for_exhaustive_opt= 7;
5685
this value could be determined by some mapping of the form:
5686
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5689
A positive integer that specifies the search depth (and thus the
5690
exhaustiveness) of the depth-first search algorithm used by
5695
determine_search_depth(JOIN *join)
5697
uint table_count= join->tables - join->const_tables;
5699
/* TODO: this value should be determined dynamically, based on statistics: */
5700
uint max_tables_for_exhaustive_opt= 7;
5702
if (table_count <= max_tables_for_exhaustive_opt)
5703
search_depth= table_count+1; // use exhaustive for small number of tables
5706
TODO: this value could be determined by some mapping of the form:
5707
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5709
search_depth= max_tables_for_exhaustive_opt; // use greedy search
5711
return search_depth;
5716
Select the best ways to access the tables in a query without reordering them.
5718
Find the best access paths for each query table and compute their costs
5719
according to their order in the array 'join->best_ref' (thus without
5720
reordering the join tables). The function calls sequentially
5721
'best_access_path' for each table in the query to select the best table
5722
access method. The final optimal plan is stored in the array
5723
'join->best_positions', and the corresponding cost in 'join->best_read'.
5725
@param join pointer to the structure providing all context info for
5727
@param join_tables set of the tables in the query
5730
This function can be applied to:
5731
- queries with STRAIGHT_JOIN
5732
- internally to compute the cost of an arbitrary QEP
5734
Thus 'optimize_straight_join' can be used at any stage of the query
5735
optimization process to finalize a QEP as it is.
5739
optimize_straight_join(JOIN *join, table_map join_tables)
5742
uint idx= join->const_tables;
5743
double record_count= 1.0;
5744
double read_time= 0.0;
5746
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
5748
/* Find the best access method from 's' to the current partial plan */
5749
advance_sj_state(join_tables, s);
5750
best_access_path(join, s, join->thd, join_tables, idx,
5751
record_count, read_time);
5752
/* compute the cost of the new plan extended with 's' */
5753
record_count*= join->positions[idx].records_read;
5754
read_time+= join->positions[idx].read_time;
5755
join_tables&= ~(s->table->map);
5759
read_time+= record_count / (double) TIME_FOR_COMPARE;
5760
if (join->sort_by_table &&
5761
join->sort_by_table != join->positions[join->const_tables].table->table)
5762
read_time+= record_count; // We have to make a temp table
5763
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
5764
join->best_read= read_time;
5769
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
5771
The search procedure uses a hybrid greedy/exhaustive search with controlled
5772
exhaustiveness. The search is performed in N = card(remaining_tables)
5773
steps. Each step evaluates how promising is each of the unoptimized tables,
5774
selects the most promising table, and extends the current partial QEP with
5775
that table. Currenly the most 'promising' table is the one with least
5776
expensive extension.\
5778
There are two extreme cases:
5779
-# When (card(remaining_tables) < search_depth), the estimate finds the
5780
best complete continuation of the partial QEP. This continuation can be
5781
used directly as a result of the search.
5782
-# When (search_depth == 1) the 'best_extension_by_limited_search'
5783
consideres the extension of the current QEP with each of the remaining
5786
All other cases are in-between these two extremes. Thus the parameter
5787
'search_depth' controlls the exhaustiveness of the search. The higher the
5788
value, the longer the optimizaton time and possibly the better the
5789
resulting plan. The lower the value, the fewer alternative plans are
5790
estimated, but the more likely to get a bad QEP.
5792
All intermediate and final results of the procedure are stored in 'join':
5793
- join->positions : modified for every partial QEP that is explored
5794
- join->best_positions: modified for the current best complete QEP
5795
- join->best_read : modified for the current best complete QEP
5796
- join->best_ref : might be partially reordered
5798
The final optimal plan is stored in 'join->best_positions', and its
5799
corresponding cost in 'join->best_read'.
5802
The following pseudocode describes the algorithm of 'greedy_search':
5805
procedure greedy_search
5806
input: remaining_tables
5811
(t, a) = best_extension(pplan, remaining_tables);
5812
pplan = concat(pplan, (t, a));
5813
remaining_tables = remaining_tables - t;
5814
} while (remaining_tables != {})
5819
where 'best_extension' is a placeholder for a procedure that selects the
5820
most "promising" of all tables in 'remaining_tables'.
5821
Currently this estimate is performed by calling
5822
'best_extension_by_limited_search' to evaluate all extensions of the
5823
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
5824
mainly depends on that of 'best_extension_by_limited_search'.
5827
If 'best_extension()' == 'best_extension_by_limited_search()', then the
5828
worst-case complexity of this algorithm is <=
5829
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
5830
complexity of greedy_search is O(N!).
5833
In the future, 'greedy_search' might be extended to support other
5834
implementations of 'best_extension', e.g. some simpler quadratic procedure.
5836
@param join pointer to the structure providing all context info
5838
@param remaining_tables set of tables not included into the partial plan yet
5839
@param search_depth controlls the exhaustiveness of the search
5840
@param prune_level the pruning heuristics that should be applied during
5850
greedy_search(JOIN *join,
5851
table_map remaining_tables,
5855
double record_count= 1.0;
5856
double read_time= 0.0;
5857
uint idx= join->const_tables; // index into 'join->best_ref'
5859
uint size_remain; // cardinality of remaining_tables
5861
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
5863
/* number of tables that remain to be optimized */
5864
size_remain= my_count_bits(remaining_tables);
5867
/* Find the extension of the current QEP with the lowest cost */
5868
join->best_read= DBL_MAX;
5869
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
5870
read_time, search_depth, prune_level))
5873
if (size_remain <= search_depth)
5876
'join->best_positions' contains a complete optimal extension of the
5877
current partial QEP.
5882
/* select the first table in the optimal extension as most promising */
5883
best_pos= join->best_positions[idx];
5884
best_table= best_pos.table;
5886
Each subsequent loop of 'best_extension_by_limited_search' uses
5887
'join->positions' for cost estimates, therefore we have to update its
5890
join->positions[idx]= best_pos;
5892
/* find the position of 'best_table' in 'join->best_ref' */
5894
JOIN_TAB *pos= join->best_ref[best_idx];
5895
while (pos && best_table != pos)
5896
pos= join->best_ref[++best_idx];
5897
assert((pos != NULL)); // should always find 'best_table'
5898
/* move 'best_table' at the first free position in the array of joins */
5899
swap_variables(JOIN_TAB*, join->best_ref[idx], join->best_ref[best_idx]);
5901
/* compute the cost of the new plan extended with 'best_table' */
5902
record_count*= join->positions[idx].records_read;
5903
read_time+= join->positions[idx].read_time;
5905
remaining_tables&= ~(best_table->table->map);
5913
Find a good, possibly optimal, query execution plan (QEP) by a possibly
5916
The procedure searches for the optimal ordering of the query tables in set
5917
'remaining_tables' of size N, and the corresponding optimal access paths to
5918
each table. The choice of a table order and an access path for each table
5919
constitutes a query execution plan (QEP) that fully specifies how to
5922
The maximal size of the found plan is controlled by the parameter
5923
'search_depth'. When search_depth == N, the resulting plan is complete and
5924
can be used directly as a QEP. If search_depth < N, the found plan consists
5925
of only some of the query tables. Such "partial" optimal plans are useful
5926
only as input to query optimization procedures, and cannot be used directly
5929
The algorithm begins with an empty partial plan stored in 'join->positions'
5930
and a set of N tables - 'remaining_tables'. Each step of the algorithm
5931
evaluates the cost of the partial plan extended by all access plans for
5932
each of the relations in 'remaining_tables', expands the current partial
5933
plan with the access plan that results in lowest cost of the expanded
5934
partial plan, and removes the corresponding relation from
5935
'remaining_tables'. The algorithm continues until it either constructs a
5936
complete optimal plan, or constructs an optimal plartial plan with size =
5939
The final optimal plan is stored in 'join->best_positions'. The
5940
corresponding cost of the optimal plan is in 'join->best_read'.
5943
The procedure uses a recursive depth-first search where the depth of the
5944
recursion (and thus the exhaustiveness of the search) is controlled by the
5945
parameter 'search_depth'.
5948
The pseudocode below describes the algorithm of
5949
'best_extension_by_limited_search'. The worst-case complexity of this
5950
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
5951
the complexity of greedy_search is O(N!).
5954
procedure best_extension_by_limited_search(
5955
pplan in, // in, partial plan of tables-joined-so-far
5956
pplan_cost, // in, cost of pplan
5957
remaining_tables, // in, set of tables not referenced in pplan
5958
best_plan_so_far, // in/out, best plan found so far
5959
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5960
search_depth) // in, maximum size of the plans being considered
5962
for each table T from remaining_tables
5964
// Calculate the cost of using table T as above
5965
cost = complex-series-of-calculations;
5967
// Add the cost to the cost so far.
5970
if (pplan_cost >= best_plan_so_far_cost)
5971
// pplan_cost already too great, stop search
5974
pplan= expand pplan by best_access_method;
5975
remaining_tables= remaining_tables - table T;
5976
if (remaining_tables is not an empty set
5980
best_extension_by_limited_search(pplan, pplan_cost,
5983
best_plan_so_far_cost,
5988
best_plan_so_far_cost= pplan_cost;
5989
best_plan_so_far= pplan;
5996
When 'best_extension_by_limited_search' is called for the first time,
5997
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
5998
The actual implementation provides a way to optionally use pruning
5999
heuristic (controlled by the parameter 'prune_level') to reduce the search
6000
space by skipping some partial plans.
6003
The parameter 'search_depth' provides control over the recursion
6004
depth, and thus the size of the resulting optimal plan.
6006
@param join pointer to the structure providing all context info
6008
@param remaining_tables set of tables not included into the partial plan yet
6009
@param idx length of the partial QEP in 'join->positions';
6010
since a depth-first search is used, also corresponds
6011
to the current depth of the search tree;
6012
also an index in the array 'join->best_ref';
6013
@param record_count estimate for the number of records returned by the
6015
@param read_time the cost of the best partial plan
6016
@param search_depth maximum depth of the recursion and thus size of the
6018
(0 < search_depth <= join->tables+1).
6019
@param prune_level pruning heuristics that should be applied during
6021
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
6030
best_extension_by_limited_search(JOIN *join,
6031
table_map remaining_tables,
6033
double record_count,
6038
THD *thd= join->thd;
6039
if (thd->killed) // Abort
6043
'join' is a partial plan with lower cost than the best plan so far,
6044
so continue expanding it further with the tables in 'remaining_tables'.
6047
double best_record_count= DBL_MAX;
6048
double best_read_time= DBL_MAX;
6050
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
6052
table_map real_table_bit= s->table->map;
6053
if ((remaining_tables & real_table_bit) &&
6054
!(remaining_tables & s->dependent) &&
6055
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6057
double current_record_count, current_read_time;
6058
advance_sj_state(remaining_tables, s);
6061
psergey-insideout-todo:
6062
when best_access_path() detects it could do an InsideOut scan or
6063
some other scan, have it return an insideout scan and a flag that
6064
requests to "fork" this loop iteration. (Q: how does that behave
6065
when the depth is insufficient??)
6067
/* Find the best access method from 's' to the current partial plan */
6068
best_access_path(join, s, thd, remaining_tables, idx,
6069
record_count, read_time);
6070
/* Compute the cost of extending the plan with 's' */
6071
current_record_count= record_count * join->positions[idx].records_read;
6072
current_read_time= read_time + join->positions[idx].read_time;
6074
/* Expand only partial plans with lower cost than the best QEP so far */
6075
if ((current_read_time +
6076
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
6078
restore_prev_nj_state(s);
6079
restore_prev_sj_state(remaining_tables, s);
6084
Prune some less promising partial plans. This heuristic may miss
6085
the optimal QEPs, thus it results in a non-exhaustive search.
6087
if (prune_level == 1)
6089
if (best_record_count > current_record_count ||
6090
best_read_time > current_read_time ||
6091
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
6093
if (best_record_count >= current_record_count &&
6094
best_read_time >= current_read_time &&
6095
/* TODO: What is the reasoning behind this condition? */
6096
(!(s->key_dependent & remaining_tables) ||
6097
join->positions[idx].records_read < 2.0))
6099
best_record_count= current_record_count;
6100
best_read_time= current_read_time;
6105
restore_prev_nj_state(s);
6106
restore_prev_sj_state(remaining_tables, s);
6111
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
6112
{ /* Recursively expand the current partial plan */
6113
swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
6114
if (best_extension_by_limited_search(join,
6115
remaining_tables & ~real_table_bit,
6117
current_record_count,
6122
swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
6126
'join' is either the best partial QEP with 'search_depth' relations,
6127
or the best complete QEP so far, whichever is smaller.
6129
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
6130
if (join->sort_by_table &&
6131
join->sort_by_table !=
6132
join->positions[join->const_tables].table->table)
6133
/* We have to make a temp table */
6134
current_read_time+= current_record_count;
6135
if ((search_depth == 1) || (current_read_time < join->best_read))
6137
memcpy(join->best_positions, join->positions,
6138
sizeof(POSITION) * (idx + 1));
6139
join->best_read= current_read_time - 0.001;
6142
restore_prev_nj_state(s);
6143
restore_prev_sj_state(remaining_tables, s);
6152
- TODO: this function is here only temporarily until 'greedy_search' is
6153
tested and accepted.
6160
find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
6163
THD *thd= join->thd;
6168
read_time+=record_count/(double) TIME_FOR_COMPARE;
6169
if (join->sort_by_table &&
6170
join->sort_by_table !=
6171
join->positions[join->const_tables].table->table)
6172
read_time+=record_count; // We have to make a temp table
6173
if (read_time < join->best_read)
6175
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
6176
join->best_read= read_time - 0.001;
6180
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
6181
return(false); /* Found better before */
6184
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
6185
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
6187
table_map real_table_bit=s->table->map;
6188
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
6189
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6191
double records, best;
6192
advance_sj_state(rest_tables, s);
6193
best_access_path(join, s, thd, rest_tables, idx, record_count,
6195
records= join->positions[idx].records_read;
6196
best= join->positions[idx].read_time;
6198
Go to the next level only if there hasn't been a better key on
6199
this level! This will cut down the search for a lot simple cases!
6201
double current_record_count=record_count*records;
6202
double current_read_time=read_time+best;
6203
if (best_record_count > current_record_count ||
6204
best_read_time > current_read_time ||
6205
(idx == join->const_tables && s->table == join->sort_by_table))
6207
if (best_record_count >= current_record_count &&
6208
best_read_time >= current_read_time &&
6209
(!(s->key_dependent & rest_tables) || records < 2.0))
6211
best_record_count=current_record_count;
6212
best_read_time=current_read_time;
6214
swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
6215
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
6216
current_record_count,current_read_time))
6218
swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
6220
restore_prev_nj_state(s);
6221
restore_prev_sj_state(rest_tables, s);
6222
if (join->select_options & SELECT_STRAIGHT_JOIN)
6223
break; // Don't test all combinations
858
6231
Find how much space the prevous read not const tables takes in cache.
860
void calc_used_field_length(Session *, JoinTable *join_tab)
6234
static void calc_used_field_length(THD *thd __attribute__((unused)),
862
uint32_t null_fields,blobs,fields,rec_length;
6237
uint null_fields,blobs,fields,rec_length;
863
6238
Field **f_ptr,*field;
6239
MY_BITMAP *read_set= join_tab->table->read_set;;
865
6241
null_fields= blobs= fields= rec_length=0;
866
6242
for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++)
868
if (field->isReadSet())
6244
if (bitmap_is_set(read_set, field->field_index))
870
uint32_t flags=field->flags;
6246
uint flags=field->flags;
872
6248
rec_length+=field->pack_length();
873
6249
if (flags & BLOB_FLAG)
875
6251
if (!(flags & NOT_NULL_FLAG))
879
6255
if (null_fields)
6838
Fill in outer join related info for the execution plan structure.
6840
For each outer join operation left after simplification of the
6841
original query the function set up the following pointers in the linear
6842
structure join->join_tab representing the selected execution plan.
6843
The first inner table t0 for the operation is set to refer to the last
6844
inner table tk through the field t0->last_inner.
6845
Any inner table ti for the operation are set to refer to the first
6846
inner table ti->first_inner.
6847
The first inner table t0 for the operation is set to refer to the
6848
first inner table of the embedding outer join operation, if there is any,
6849
through the field t0->first_upper.
6850
The on expression for the outer join operation is attached to the
6851
corresponding first inner table through the field t0->on_expr_ref.
6852
Here ti are structures of the JOIN_TAB type.
6854
EXAMPLE. For the query:
6858
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
6859
ON (t1.a=t2.a AND t1.b=t3.b)
6863
given the execution plan with the table order t1,t2,t3,t4
6864
is selected, the following references will be set;
6865
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
6866
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
6867
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
6868
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
6870
@param join reference to the info fully describing the query
6873
The function assumes that the simplification procedure has been
6874
already applied to the join query (see simplify_joins).
6875
This function can be called only after the execution plan
6880
make_outerjoin_info(JOIN *join)
6882
for (uint i=join->const_tables ; i < join->tables ; i++)
6884
JOIN_TAB *tab=join->join_tab+i;
6885
TABLE *table=tab->table;
6886
TABLE_LIST *tbl= table->pos_in_table_list;
6887
TABLE_LIST *embedding= tbl->embedding;
6889
if (tbl->outer_join)
6892
Table tab is the only one inner table for outer join.
6893
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
6894
is in the query above.)
6896
tab->last_inner= tab->first_inner= tab;
6897
tab->on_expr_ref= &tbl->on_expr;
6898
tab->cond_equal= tbl->cond_equal;
6900
tab->first_upper= embedding->nested_join->first_nested;
6902
for ( ; embedding ; embedding= embedding->embedding)
6904
/* Ignore sj-nests: */
6905
if (!embedding->on_expr)
6907
NESTED_JOIN *nested_join= embedding->nested_join;
6908
if (!nested_join->counter_)
6911
Table tab is the first inner table for nested_join.
6912
Save reference to it in the nested join structure.
6914
nested_join->first_nested= tab;
6915
tab->on_expr_ref= &embedding->on_expr;
6916
tab->cond_equal= tbl->cond_equal;
6917
if (embedding->embedding)
6918
tab->first_upper= embedding->embedding->nested_join->first_nested;
6920
if (!tab->first_inner)
6921
tab->first_inner= nested_join->first_nested;
6922
if (++nested_join->counter_ < nested_join->join_list.elements)
6924
/* Table tab is the last inner table for nested join. */
6925
nested_join->first_nested->last_inner= tab;
6933
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
6935
THD *thd= join->thd;
6938
add_not_null_conds(join);
6939
table_map used_tables;
6940
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
6941
{ /* there may be a select without a cond. */
6942
if (join->tables > 1)
6943
cond->update_used_tables(); // Tablenr may have changed
6944
if (join->const_tables == join->tables &&
6945
thd->lex->current_select->master_unit() ==
6946
&thd->lex->unit) // not upper level SELECT
6947
join->const_table_map|=RAND_TABLE_BIT;
6948
{ // Check const tables
6950
make_cond_for_table(cond,
6951
join->const_table_map,
6953
for (JOIN_TAB *tab= join->join_tab+join->const_tables;
6954
tab < join->join_tab+join->tables ; tab++)
6956
if (*tab->on_expr_ref)
6958
JOIN_TAB *cond_tab= tab->first_inner;
6959
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
6960
join->const_table_map,
6964
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
6967
tmp->quick_fix_field();
6968
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
6969
new Item_cond_and(cond_tab->select_cond,
6971
if (!cond_tab->select_cond)
6973
cond_tab->select_cond->quick_fix_field();
6976
if (const_cond && !const_cond->val_int())
6978
return(1); // Impossible const condition
6982
used_tables=((select->const_tables=join->const_table_map) |
6983
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
6984
for (uint i=join->const_tables ; i < join->tables ; i++)
6986
JOIN_TAB *tab=join->join_tab+i;
6988
first_inner is the X in queries like:
6989
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
6991
JOIN_TAB *first_inner_tab= tab->first_inner;
6992
table_map current_map= tab->table->map;
6993
bool use_quick_range=0;
6997
Following force including random expression in last table condition.
6998
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
7000
if (i == join->tables-1)
7001
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
7002
used_tables|=current_map;
7004
if (tab->type == JT_REF && tab->quick &&
7005
(uint) tab->ref.key == tab->quick->index &&
7006
tab->ref.key_length < tab->quick->max_used_key_length)
7008
/* Range uses longer key; Use this instead of ref on key */
7013
tab->ref.key_parts=0; // Don't use ref key.
7014
join->best_positions[i].records_read= rows2double(tab->quick->records);
7016
We will use join cache here : prevent sorting of the first
7017
table only and sort at the end.
7019
if (i != join->const_tables && join->tables > join->const_tables + 1)
7025
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
7026
if (cond && !tmp && tab->quick)
7028
if (tab->type != JT_ALL)
7031
Don't use the quick method
7032
We come here in the case where we have 'key=constant' and
7033
the test is removed by make_cond_for_table()
7041
Hack to handle the case where we only refer to a table
7042
in the ON part of an OUTER JOIN. In this case we want the code
7043
below to check if we should use 'quick' instead.
7045
tmp= new Item_int((int64_t) 1,1); // Always true
7049
if (tmp || !cond || tab->type == JT_REF || tab->type == JT_REF_OR_NULL ||
7050
tab->type == JT_EQ_REF)
7052
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
7053
thd->memdup((uchar*) select,
7056
return(1); // End of memory
7058
If tab is an inner table of an outer join operation,
7059
add a match guard to the pushed down predicate.
7060
The guard will turn the predicate on only after
7061
the first match for outer tables is encountered.
7066
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
7067
a cond, so neutralize the hack above.
7069
if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
7071
tab->select_cond=sel->cond=tmp;
7072
/* Push condition to storage engine if this is enabled
7073
and the condition is not guarded */
7074
tab->table->file->pushed_cond= NULL;
7075
if (thd->variables.engine_condition_pushdown)
7078
make_cond_for_table(tmp, current_map, current_map, 0);
7081
/* Push condition to handler */
7082
if (!tab->table->file->cond_push(push_cond))
7083
tab->table->file->pushed_cond= push_cond;
7088
tab->select_cond= sel->cond= NULL;
7090
sel->head=tab->table;
7093
/* Use quick key read if it's a constant and it's not used
7095
if (tab->needed_reg.is_clear_all() && tab->type != JT_EQ_REF
7096
&& (tab->type != JT_REF || (uint) tab->ref.key == tab->quick->index))
7098
sel->quick=tab->quick; // Use value from get_quick_...
7099
sel->quick_keys.clear_all();
7100
sel->needed_reg.clear_all();
7108
uint ref_key=(uint) sel->head->reginfo.join_tab->ref.key+1;
7109
if (i == join->const_tables && ref_key)
7111
if (!tab->const_keys.is_clear_all() &&
7112
tab->table->reginfo.impossible_range)
7115
else if (tab->type == JT_ALL && ! use_quick_range)
7117
if (!tab->const_keys.is_clear_all() &&
7118
tab->table->reginfo.impossible_range)
7119
return(1); // Impossible range
7121
We plan to scan all rows.
7122
Check again if we should use an index.
7123
We could have used an column from a previous table in
7124
the index if we are using limit and this is the first table
7127
if ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||
7128
(!tab->const_keys.is_clear_all() && (i == join->const_tables) && (join->unit->select_limit_cnt < join->best_positions[i].records_read) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
7130
/* Join with outer join condition */
7131
COND *orig_cond=sel->cond;
7132
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
7135
We can't call sel->cond->fix_fields,
7136
as it will break tab->on_expr if it's AND condition
7137
(fix_fields currently removes extra AND/OR levels).
7138
Yet attributes of the just built condition are not needed.
7139
Thus we call sel->cond->quick_fix_field for safety.
7141
if (sel->cond && !sel->cond->fixed)
7142
sel->cond->quick_fix_field();
7144
if (sel->test_quick_select(thd, tab->keys,
7145
used_tables & ~ current_map,
7146
(join->select_options &
7149
join->unit->select_limit_cnt), 0,
7153
Before reporting "Impossible WHERE" for the whole query
7154
we have to check isn't it only "impossible ON" instead
7156
sel->cond=orig_cond;
7157
if (!*tab->on_expr_ref ||
7158
sel->test_quick_select(thd, tab->keys,
7159
used_tables & ~ current_map,
7160
(join->select_options &
7163
join->unit->select_limit_cnt),0,
7165
return(1); // Impossible WHERE
7168
sel->cond=orig_cond;
7170
/* Fix for EXPLAIN */
7172
join->best_positions[i].records_read= (double)sel->quick->records;
7176
sel->needed_reg=tab->needed_reg;
7177
sel->quick_keys.clear_all();
7179
if (!sel->quick_keys.is_subset(tab->checked_keys) ||
7180
!sel->needed_reg.is_subset(tab->checked_keys))
7182
tab->keys=sel->quick_keys;
7183
tab->keys.merge(sel->needed_reg);
7184
tab->use_quick= (!sel->needed_reg.is_clear_all() &&
7185
(select->quick_keys.is_clear_all() ||
7187
(select->quick->records >= 100L)))) ?
7189
sel->read_tables= used_tables & ~current_map;
7191
if (i != join->const_tables && tab->use_quick != 2)
7192
{ /* Read with cache */
7194
(tmp=make_cond_for_table(cond,
7195
join->const_table_map |
7199
tab->cache.select=(SQL_SELECT*)
7200
thd->memdup((uchar*) sel, sizeof(SQL_SELECT));
7201
tab->cache.select->cond=tmp;
7202
tab->cache.select->read_tables=join->const_table_map;
7209
Push down conditions from all on expressions.
7210
Each of these conditions are guarded by a variable
7211
that turns if off just before null complemented row for
7212
outer joins is formed. Thus, the condition from an
7213
'on expression' are guaranteed not to be checked for
7214
the null complemented row.
7217
/* First push down constant conditions from on expressions */
7218
for (JOIN_TAB *join_tab= join->join_tab+join->const_tables;
7219
join_tab < join->join_tab+join->tables ; join_tab++)
7221
if (*join_tab->on_expr_ref)
7223
JOIN_TAB *cond_tab= join_tab->first_inner;
7224
COND *tmp= make_cond_for_table(*join_tab->on_expr_ref,
7225
join->const_table_map,
7229
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
7232
tmp->quick_fix_field();
7233
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
7234
new Item_cond_and(cond_tab->select_cond,tmp);
7235
if (!cond_tab->select_cond)
7237
cond_tab->select_cond->quick_fix_field();
7241
/* Push down non-constant conditions from on expressions */
7242
JOIN_TAB *last_tab= tab;
7243
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
7246
Table tab is the last inner table of an outer join.
7247
An on expression is always attached to it.
7249
COND *on_expr= *first_inner_tab->on_expr_ref;
7251
table_map used_tables2= (join->const_table_map |
7252
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7253
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
7255
current_map= tab->table->map;
7256
used_tables2|= current_map;
7257
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
7261
JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
7263
First add the guards for match variables of
7264
all embedding outer join operations.
7266
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
7271
Now add the guard turning the predicate off for
7272
the null complemented row.
7274
tmp_cond= new Item_func_trig_cond(tmp_cond,
7278
tmp_cond->quick_fix_field();
7279
/* Add the predicate to other pushed down predicates */
7280
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
7281
new Item_cond_and(cond_tab->select_cond,
7283
if (!cond_tab->select_cond)
7285
cond_tab->select_cond->quick_fix_field();
7288
first_inner_tab= first_inner_tab->first_upper;
1226
7297
Check if given expression uses only table fields covered by the given index
2755
9617
if (!(left_const && right_const) &&
2756
9618
args[0]->result_type() == args[1]->result_type())
2760
resolve_const_item(session, &args[1], args[0]);
2761
func->update_used_tables();
2762
change_cond_ref_to_const(session, save_list, and_father, and_father,
2765
else if (left_const)
2767
resolve_const_item(session, &args[0], args[1]);
2768
func->update_used_tables();
2769
change_cond_ref_to_const(session, save_list, and_father, and_father,
9622
resolve_const_item(thd, &args[1], args[0]);
9623
func->update_used_tables();
9624
change_cond_ref_to_const(thd, save_list, and_father, and_father,
9627
else if (left_const)
9629
resolve_const_item(thd, &args[0], args[1]);
9630
func->update_used_tables();
9631
change_cond_ref_to_const(thd, save_list, and_father, and_father,
9641
Simplify joins replacing outer joins by inner joins whenever it's
9644
The function, during a retrieval of join_list, eliminates those
9645
outer joins that can be converted into inner join, possibly nested.
9646
It also moves the on expressions for the converted outer joins
9647
and from inner joins to conds.
9648
The function also calculates some attributes for nested joins:
9652
- on_expr_dep_tables
9653
The first two attributes are used to test whether an outer join can
9654
be substituted for an inner join. The third attribute represents the
9655
relation 'to be dependent on' for tables. If table t2 is dependent
9656
on table t1, then in any evaluated execution plan table access to
9657
table t2 must precede access to table t2. This relation is used also
9658
to check whether the query contains invalid cross-references.
9659
The forth attribute is an auxiliary one and is used to calculate
9661
As the attribute dep_tables qualifies possibles orders of tables in the
9662
execution plan, the dependencies required by the straight join
9663
modifiers are reflected in this attribute as well.
9664
The function also removes all braces that can be removed from the join
9665
expression without changing its meaning.
9668
An outer join can be replaced by an inner join if the where condition
9669
or the on expression for an embedding nested join contains a conjunctive
9670
predicate rejecting null values for some attribute of the inner tables.
9674
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9676
the predicate t2.b < 5 rejects nulls.
9677
The query is converted first to:
9679
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9681
then to the equivalent form:
9683
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
9687
Similarly the following query:
9689
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
9694
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
9698
One conversion might trigger another:
9700
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
9701
LEFT JOIN t3 ON t3.b=t2.b
9702
WHERE t3 IS NOT NULL =>
9703
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
9704
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
9705
SELECT * FROM t1, t2, t3
9706
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
9709
The function removes all unnecessary braces from the expression
9710
produced by the conversions.
9713
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9715
finally is converted to:
9717
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9722
It also will remove braces from the following queries:
9724
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
9725
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
9728
The benefit of this simplification procedure is that it might return
9729
a query for which the optimizer can evaluate execution plan with more
9730
join orders. With a left join operation the optimizer does not
9731
consider any plan where one of the inner tables is before some of outer
9735
The function is implemented by a recursive procedure. On the recursive
9736
ascent all attributes are calculated, all outer joins that can be
9737
converted are replaced and then all unnecessary braces are removed.
9738
As join list contains join tables in the reverse order sequential
9739
elimination of outer joins does not require extra recursive calls.
9742
Remove all semi-joins that have are within another semi-join (i.e. have
9743
an "ancestor" semi-join nest)
9746
Here is an example of a join query with invalid cross references:
9748
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
9751
@param join reference to the query info
9752
@param join_list list representation of the join to be converted
9753
@param conds conditions to add on expressions for converted joins
9754
@param top true <=> conds is the where condition
9757
- The new condition, if success
9762
simplify_joins(JOIN *join, List<TABLE_LIST> *join_list, COND *conds, bool top,
9766
NESTED_JOIN *nested_join;
9767
TABLE_LIST *prev_table= 0;
9768
List_iterator<TABLE_LIST> li(*join_list);
9771
Try to simplify join operations from join_list.
9772
The most outer join operation is checked for conversion first.
9774
while ((table= li++))
9776
table_map used_tables;
9777
table_map not_null_tables= (table_map) 0;
9779
if ((nested_join= table->nested_join))
9782
If the element of join_list is a nested join apply
9783
the procedure to its nested join list first.
9787
Item *expr= table->on_expr;
9789
If an on expression E is attached to the table,
9790
check all null rejected predicates in this expression.
9791
If such a predicate over an attribute belonging to
9792
an inner table of an embedded outer join is found,
9793
the outer join is converted to an inner join and
9794
the corresponding on expression is added to E.
9796
expr= simplify_joins(join, &nested_join->join_list,
9797
expr, false, in_sj || table->sj_on_expr);
9799
if (!table->prep_on_expr || expr != table->on_expr)
9803
table->on_expr= expr;
9804
table->prep_on_expr= expr->copy_andor_structure(join->thd);
9807
nested_join->used_tables= (table_map) 0;
9808
nested_join->not_null_tables=(table_map) 0;
9809
conds= simplify_joins(join, &nested_join->join_list, conds, top,
9810
in_sj || table->sj_on_expr);
9811
used_tables= nested_join->used_tables;
9812
not_null_tables= nested_join->not_null_tables;
9816
if (!table->prep_on_expr)
9817
table->prep_on_expr= table->on_expr;
9818
used_tables= table->table->map;
9820
not_null_tables= conds->not_null_tables();
9823
if (table->embedding)
9825
table->embedding->nested_join->used_tables|= used_tables;
9826
table->embedding->nested_join->not_null_tables|= not_null_tables;
9829
if (!table->outer_join || (used_tables & not_null_tables))
9832
For some of the inner tables there are conjunctive predicates
9833
that reject nulls => the outer join can be replaced by an inner join.
9835
table->outer_join= 0;
9838
/* Add ON expression to the WHERE or upper-level ON condition. */
9841
conds= and_conds(conds, table->on_expr);
9842
conds->top_level_item();
9843
/* conds is always a new item as both cond and on_expr existed */
9844
assert(!conds->fixed);
9845
conds->fix_fields(join->thd, &conds);
9848
conds= table->on_expr;
9849
table->prep_on_expr= table->on_expr= 0;
9857
Only inner tables of non-convertible outer joins
9858
remain with on_expr.
9862
table->dep_tables|= table->on_expr->used_tables();
9863
if (table->embedding)
9865
table->dep_tables&= ~table->embedding->nested_join->used_tables;
9867
Embedding table depends on tables used
9868
in embedded on expressions.
9870
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
9873
table->dep_tables&= ~table->table->map;
9878
/* The order of tables is reverse: prev_table follows table */
9879
if (prev_table->straight)
9880
prev_table->dep_tables|= used_tables;
9881
if (prev_table->on_expr)
9883
prev_table->dep_tables|= table->on_expr_dep_tables;
9884
table_map prev_used_tables= prev_table->nested_join ?
9885
prev_table->nested_join->used_tables :
9886
prev_table->table->map;
9888
If on expression contains only references to inner tables
9889
we still make the inner tables dependent on the outer tables.
9890
It would be enough to set dependency only on one outer table
9891
for them. Yet this is really a rare case.
9893
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
9894
prev_table->dep_tables|= used_tables;
9901
Flatten nested joins that can be flattened.
9902
no ON expression and not a semi-join => can be flattened.
9905
while ((table= li++))
9907
nested_join= table->nested_join;
9908
if (table->sj_on_expr && !in_sj)
9911
If this is a semi-join that is not contained within another semi-join,
9912
leave it intact (otherwise it is flattened)
9914
join->select_lex->sj_nests.push_back(table);
9916
else if (nested_join && !table->on_expr)
9919
List_iterator<TABLE_LIST> it(nested_join->join_list);
9922
tbl->embedding= table->embedding;
9923
tbl->join_list= table->join_list;
9925
li.replace(nested_join->join_list);
9933
Assign each nested join structure a bit in nested_join_map.
9935
Assign each nested join structure (except "confluent" ones - those that
9936
embed only one element) a bit in nested_join_map.
9938
@param join Join being processed
9939
@param join_list List of tables
9940
@param first_unused Number of first unused bit in nested_join_map before the
9944
This function is called after simplify_joins(), when there are no
9945
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
9946
we will not run out of bits in nested_join_map.
9949
First unused bit in nested_join_map after the call.
9952
static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list,
9955
List_iterator<TABLE_LIST> li(*join_list);
9957
while ((table= li++))
9959
NESTED_JOIN *nested_join;
9960
if ((nested_join= table->nested_join))
9963
It is guaranteed by simplify_joins() function that a nested join
9964
that has only one child is either
9965
- a single-table view (the child is the underlying table), or
9966
- a single-table semi-join nest
9968
We don't assign bits to such sj-nests because
9969
1. it is redundant (a "sequence" of one table cannot be interleaved
9971
2. we could run out bits in nested_join_map otherwise.
9973
if (nested_join->join_list.elements != 1)
9975
/* Don't assign bits to sj-nests */
9977
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
9978
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
9983
return(first_unused);
9988
Set NESTED_JOIN::counter=0 in all nested joins in passed list.
9990
Recursively set NESTED_JOIN::counter=0 for all nested joins contained in
9991
the passed join_list.
9993
@param join_list List of nested joins to process. It may also contain base
9994
tables which will be ignored.
9997
static void reset_nj_counters(List<TABLE_LIST> *join_list)
9999
List_iterator<TABLE_LIST> li(*join_list);
10001
while ((table= li++))
10003
NESTED_JOIN *nested_join;
10004
if ((nested_join= table->nested_join))
10006
nested_join->counter_= 0;
10007
reset_nj_counters(&nested_join->join_list);
2778
10015
Check interleaving with an inner tables of an outer join for
2779
10016
extension table.
2781
Check if table next_tab can be added to current partial join order, and
10018
Check if table next_tab can be added to current partial join order, and
2782
10019
if yes, record that it has been added.
2784
10021
The function assumes that both current partial join order and its
2785
10022
extension with next_tab are valid wrt table dependencies.
2789
LIMITATIONS ON JOIN order_st
10026
LIMITATIONS ON JOIN ORDER
2790
10027
The nested [outer] joins executioner algorithm imposes these limitations
2791
10028
on join order:
2792
1. "Outer tables first" - any "outer" table must be before any
10029
1. "Outer tables first" - any "outer" table must be before any
2793
10030
corresponding "inner" table.
2794
10031
2. "No interleaving" - tables inside a nested join must form a continuous
2795
sequence in join order (i.e. the sequence must not be interrupted by
10032
sequence in join order (i.e. the sequence must not be interrupted by
2796
10033
tables that are outside of this nested join).
2798
10035
#1 is checked elsewhere, this function checks #2 provided that #1 has
2799
10036
been already checked.
2801
10038
WHY NEED NON-INTERLEAVING
2802
Consider an example:
10039
Consider an example:
2804
10041
select * from t0 join t1 left join (t2 join t3) on cond1
3596
int safe_index_read(JoinTable *tab)
3599
Table *table= tab->table;
3600
if ((error=table->cursor->index_read_map(table->record[0],
10921
SemiJoinDuplicateElimination: Weed out duplicate row combinations
10924
do_sj_dups_weedout()
10928
1 The row combination is a duplicate (discard it)
10929
0 The row combination is not a duplicate (continue)
10932
int do_sj_dups_weedout(THD *thd, SJ_TMP_TABLE *sjtbl)
10935
SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
10936
SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
10937
uchar *ptr= sjtbl->tmp_table->record[0] + 1;
10938
uchar *nulls_ptr= ptr;
10940
/* Put the the rowids tuple into table->record[0]: */
10942
// 1. Store the length
10943
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
10945
*ptr= (uchar)(sjtbl->rowid_len + sjtbl->null_bytes);
10950
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
10954
// 2. Zero the null bytes
10955
if (sjtbl->null_bytes)
10957
memset(ptr, 0, sjtbl->null_bytes);
10958
ptr += sjtbl->null_bytes;
10961
// 3. Put the rowids
10962
for (uint i=0; tab != tab_end; tab++, i++)
10964
handler *h= tab->join_tab->table->file;
10965
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
10967
/* It's a NULL-complemented row */
10968
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
10969
memset(ptr + tab->rowid_offset, 0, h->ref_length);
10973
/* Copy the rowid value */
10974
if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
10975
h->position(tab->join_tab->table->record[0]);
10976
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
10980
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
10983
/* create_myisam_from_heap will generate error if needed */
10984
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
10985
create_myisam_from_heap(thd, sjtbl->tmp_table, sjtbl->start_recinfo,
10986
&sjtbl->recinfo, error, 1))
10988
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
10996
SemiJoinDuplicateElimination: Reset the temporary table
10999
int do_sj_reset(SJ_TMP_TABLE *sj_tbl)
11001
if (sj_tbl->tmp_table)
11002
return sj_tbl->tmp_table->file->ha_delete_all_rows();
11007
Process one record of the nested loop join.
11009
This function will evaluate parts of WHERE/ON clauses that are
11010
applicable to the partial record on hand and in case of success
11011
submit this record to the next level of the nested loop.
11014
static enum_nested_loop_state
11015
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
11018
bool not_used_in_distinct=join_tab->not_used_in_distinct;
11019
ha_rows found_records=join->found_records;
11020
COND *select_cond= join_tab->select_cond;
11022
if (error > 0 || (join->thd->is_error())) // Fatal error
11023
return NESTED_LOOP_ERROR;
11025
return NESTED_LOOP_NO_MORE_ROWS;
11026
if (join->thd->killed) // Aborted by user
11028
join->thd->send_kill_message();
11029
return NESTED_LOOP_KILLED; /* purecov: inspected */
11031
if (!select_cond || select_cond->val_int())
11034
There is no select condition or the attached pushed down
11035
condition is true => a match is found.
11038
while (join_tab->first_unmatched && found)
11041
The while condition is always false if join_tab is not
11042
the last inner join table of an outer join operation.
11044
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11046
Mark that a match for current outer table is found.
11047
This activates push down conditional predicates attached
11048
to the all inner tables of the outer join.
11050
first_unmatched->found= 1;
11051
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11053
if (tab->table->reginfo.not_exists_optimize)
11054
return NESTED_LOOP_NO_MORE_ROWS;
11055
/* Check all predicates that has just been activated. */
11057
Actually all predicates non-guarded by first_unmatched->found
11058
will be re-evaluated again. It could be fixed, but, probably,
11059
it's not worth doing now.
11061
if (tab->select_cond && !tab->select_cond->val_int())
11063
/* The condition attached to table tab is false */
11064
if (tab == join_tab)
11069
Set a return point if rejected predicate is attached
11070
not to the last table of the current nest level.
11072
join->return_tab= tab;
11073
return NESTED_LOOP_OK;
11078
Check whether join_tab is not the last inner table
11079
for another embedding outer join.
11081
if ((first_unmatched= first_unmatched->first_upper) &&
11082
first_unmatched->last_inner != join_tab)
11083
first_unmatched= 0;
11084
join_tab->first_unmatched= first_unmatched;
11087
JOIN_TAB *return_tab= join->return_tab;
11088
join_tab->found_match= true;
11089
if (join_tab->check_weed_out_table)
11091
int res= do_sj_dups_weedout(join->thd, join_tab->check_weed_out_table);
11093
return NESTED_LOOP_ERROR;
11095
return NESTED_LOOP_OK;
11097
else if (join_tab->do_firstmatch)
11100
We should return to the join_tab->do_firstmatch after we have
11101
enumerated all the suffixes for current prefix row combination
11103
return_tab= join_tab->do_firstmatch;
11107
It was not just a return to lower loop level when one
11108
of the newly activated predicates is evaluated as false
11109
(See above join->return_tab= tab).
11111
join->examined_rows++;
11112
join->thd->row_count++;
11116
enum enum_nested_loop_state rc;
11117
/* A match from join_tab is found for the current partial join. */
11118
rc= (*join_tab->next_select)(join, join_tab+1, 0);
11119
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11121
if (return_tab < join->return_tab)
11122
join->return_tab= return_tab;
11124
if (join->return_tab < join_tab)
11125
return NESTED_LOOP_OK;
11127
Test if this was a SELECT DISTINCT query on a table that
11128
was not in the field list; In this case we can abort if
11129
we found a row, as no new rows can be added to the result.
11131
if (not_used_in_distinct && found_records != join->found_records)
11132
return NESTED_LOOP_NO_MORE_ROWS;
11135
join_tab->read_record.file->unlock_row();
11140
The condition pushed down to the table join_tab rejects all rows
11141
with the beginning coinciding with the current partial join.
11143
join->examined_rows++;
11144
join->thd->row_count++;
11145
join_tab->read_record.file->unlock_row();
11147
return NESTED_LOOP_OK;
11154
Construct a NULL complimented partial join record and feed it to the next
11155
level of the nested loop. This function is used in case we have
11156
an OUTER join and no matching record was found.
11159
static enum_nested_loop_state
11160
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab)
11163
The table join_tab is the first inner table of a outer join operation
11164
and no matches has been found for the current outer row.
11166
JOIN_TAB *last_inner_tab= join_tab->last_inner;
11167
/* Cache variables for faster loop */
11169
for ( ; join_tab <= last_inner_tab ; join_tab++)
11171
/* Change the the values of guard predicate variables. */
11172
join_tab->found= 1;
11173
join_tab->not_null_compl= 0;
11174
/* The outer row is complemented by nulls for each inner tables */
11175
restore_record(join_tab->table,s->default_values); // Make empty record
11176
mark_as_null_row(join_tab->table); // For group by without error
11177
select_cond= join_tab->select_cond;
11178
/* Check all attached conditions for inner table rows. */
11179
if (select_cond && !select_cond->val_int())
11180
return NESTED_LOOP_OK;
11184
The row complemented by nulls might be the first row
11185
of embedding outer joins.
11186
If so, perform the same actions as in the code
11187
for the first regular outer join row above.
11191
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11192
if ((first_unmatched= first_unmatched->first_upper) &&
11193
first_unmatched->last_inner != join_tab)
11194
first_unmatched= 0;
11195
join_tab->first_unmatched= first_unmatched;
11196
if (!first_unmatched)
11198
first_unmatched->found= 1;
11199
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11201
if (tab->select_cond && !tab->select_cond->val_int())
11203
join->return_tab= tab;
11204
return NESTED_LOOP_OK;
11209
The row complemented by nulls satisfies all conditions
11210
attached to inner tables.
11211
Send the row complemented by nulls to be joined with the
11214
return (*join_tab->next_select)(join, join_tab+1, 0);
11218
static enum_nested_loop_state
11219
flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skip_last)
11221
enum_nested_loop_state rc= NESTED_LOOP_OK;
11225
join_tab->table->null_row= 0;
11226
if (!join_tab->cache.records)
11227
return NESTED_LOOP_OK; /* Nothing to do */
11229
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
11230
if (join_tab->use_quick == 2)
11232
if (join_tab->select->quick)
11233
{ /* Used quick select last. reset it */
11234
delete join_tab->select->quick;
11235
join_tab->select->quick=0;
11238
/* read through all records */
11239
if ((error=join_init_read_record(join_tab)))
11241
reset_cache_write(&join_tab->cache);
11242
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
11245
for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
11247
tmp->status=tmp->table->status;
11248
tmp->table->status=0;
11251
info= &join_tab->read_record;
11254
if (join->thd->killed)
11256
join->thd->send_kill_message();
11257
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
11259
SQL_SELECT *select=join_tab->select;
11260
if (rc == NESTED_LOOP_OK &&
11261
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
11264
reset_cache_read(&join_tab->cache);
11265
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
11267
read_cached_record(join_tab);
11268
if (!select || !select->skip_record())
11271
if (!join_tab->check_weed_out_table ||
11272
!(res= do_sj_dups_weedout(join->thd, join_tab->check_weed_out_table)))
11274
rc= (join_tab->next_select)(join,join_tab+1,0);
11275
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11277
reset_cache_write(&join_tab->cache);
11282
return NESTED_LOOP_ERROR;
11286
} while (!(error=info->read_record(info)));
11289
read_cached_record(join_tab); // Restore current record
11290
reset_cache_write(&join_tab->cache);
11291
if (error > 0) // Fatal error
11292
return NESTED_LOOP_ERROR; /* purecov: inspected */
11293
for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
11294
tmp2->table->status=tmp2->status;
11295
return NESTED_LOOP_OK;
11299
/*****************************************************************************
11300
The different ways to read a record
11301
Returns -1 if row was not found, 0 if row was found and 1 on errors
11302
*****************************************************************************/
11304
/** Help function when we get some an error from the table handler. */
11306
int report_error(TABLE *table, int error)
11308
if (error == HA_ERR_END_OF_FILE || error == HA_ERR_KEY_NOT_FOUND)
11310
table->status= STATUS_GARBAGE;
11311
return -1; // key not found; ok
11314
Locking reads can legally return also these errors, do not
11315
print them to the .err log
11317
if (error != HA_ERR_LOCK_DEADLOCK && error != HA_ERR_LOCK_WAIT_TIMEOUT)
11318
sql_print_error("Got error %d when reading table '%s'",
11319
error, table->s->path.str);
11320
table->file->print_error(error,MYF(0));
11325
int safe_index_read(JOIN_TAB *tab)
11328
TABLE *table= tab->table;
11329
if ((error=table->file->index_read_map(table->record[0],
3601
11330
tab->ref.key_buff,
3602
11331
make_prev_keypart_map(tab->ref.key_parts),
3603
11332
HA_READ_KEY_EXACT)))
3604
return table->report_error(error);
11333
return report_error(table, error);
3608
int join_read_const_table(JoinTable *tab, optimizer::Position *pos)
11339
join_read_const_table(JOIN_TAB *tab, POSITION *pos)
3611
Table *table=tab->table;
11342
TABLE *table=tab->table;
3612
11343
table->const_table=1;
3613
11344
table->null_row=0;
3614
11345
table->status=STATUS_NO_RECORD;
3616
if (tab->type == AM_SYSTEM)
11347
if (tab->type == JT_SYSTEM)
3618
11349
if ((error=join_read_system(tab)))
3619
11350
{ // Info for DESCRIBE
3620
11351
tab->info="const row not found";
3621
11352
/* Mark for EXPLAIN that the row was not found */
3622
pos->setFanout(0.0);
3623
pos->clearRefDependMap();
3624
if (! table->maybe_null || error > 0)
11353
pos->records_read=0.0;
11354
pos->ref_depend_map= 0;
11355
if (!table->maybe_null || error > 0)
3630
if (! table->key_read &&
3631
table->covering_keys.test(tab->ref.key) &&
3632
! table->no_keyread &&
3633
(int) table->reginfo.lock_type <= (int) TL_READ_WITH_SHARED_LOCKS)
11361
if (!table->key_read && table->covering_keys.is_set(tab->ref.key) &&
11362
!table->no_keyread &&
11363
(int) table->reginfo.lock_type <= (int) TL_READ_HIGH_PRIORITY)
3635
11365
table->key_read=1;
3636
table->cursor->extra(HA_EXTRA_KEYREAD);
11366
table->file->extra(HA_EXTRA_KEYREAD);
3637
11367
tab->index= tab->ref.key;
3639
11369
error=join_read_const(tab);
3640
11370
if (table->key_read)
3642
11372
table->key_read=0;
3643
table->cursor->extra(HA_EXTRA_NO_KEYREAD);
11373
table->file->extra(HA_EXTRA_NO_KEYREAD);
3647
11377
tab->info="unique row not found";
3648
11378
/* Mark for EXPLAIN that the row was not found */
3649
pos->setFanout(0.0);
3650
pos->clearRefDependMap();
11379
pos->records_read=0.0;
11380
pos->ref_depend_map= 0;
3651
11381
if (!table->maybe_null || error > 0)
3655
11385
if (*tab->on_expr_ref && !table->null_row)
3657
11387
if ((table->null_row= test((*tab->on_expr_ref)->val_int() == 0)))
3658
table->mark_as_null_row();
11388
mark_as_null_row(table);
3660
11390
if (!table->null_row)
3661
11391
table->maybe_null=0;