20
20
mysql_select and join optimization
23
22
@defgroup Query_Optimizer Query Optimizer
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>
32
#include <libdrizzle/gettext.h>
34
const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
35
"MAYBE_REF","ALL","range","index",
36
"ref_or_null","unique_subquery","index_subquery",
25
#include "drizzled/server_includes.h"
26
#include "drizzled/sql_select.h" /* include join.h */
27
#include "drizzled/table_map_iterator.h"
29
#include "drizzled/error.h"
30
#include "drizzled/gettext.h"
31
#include "drizzled/util/test.h"
32
#include "drizzled/name_resolution_context_state.h"
33
#include "drizzled/nested_join.h"
34
#include "drizzled/probes.h"
35
#include "drizzled/show.h"
36
#include "drizzled/plugin/info_schema_table.h"
37
#include "drizzled/item/cache.h"
38
#include "drizzled/item/cmpfunc.h"
39
#include "drizzled/item/copy_string.h"
40
#include "drizzled/item/uint.h"
41
#include "drizzled/cached_item.h"
42
#include "drizzled/sql_base.h"
43
#include "drizzled/field/blob.h"
44
#include "drizzled/check_stack_overrun.h"
45
#include "drizzled/lock.h"
46
#include "drizzled/item/outer_ref.h"
47
#include "drizzled/index_hint.h"
49
#include "drizzled/sql_union.h"
50
#include "drizzled/optimizer/key_field.h"
51
#include "drizzled/optimizer/position.h"
52
#include "drizzled/optimizer/sargable_param.h"
53
#include "drizzled/optimizer/key_use.h"
61
using namespace drizzled;
63
static const string access_method_str[]=
40
struct st_sargable_param;
42
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
43
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds,
44
DYNAMIC_ARRAY *keyuse);
45
static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,
47
uint32_t tables, COND *conds,
48
COND_EQUAL *cond_equal,
49
table_map table_map, SELECT_LEX *select_lex,
50
st_sargable_param **sargables);
51
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
52
static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);
53
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
54
table_map used_tables);
55
static bool choose_plan(JOIN *join,table_map join_tables);
57
static void best_access_path(JOIN *join, JOIN_TAB *s, THD *thd,
58
table_map remaining_tables, uint32_t idx,
59
double record_count, double read_time);
60
static void optimize_straight_join(JOIN *join, table_map join_tables);
61
static bool greedy_search(JOIN *join, table_map remaining_tables,
62
uint32_t depth, uint32_t prune_level);
63
static bool best_extension_by_limited_search(JOIN *join,
64
table_map remaining_tables,
65
uint32_t idx, double record_count,
66
double read_time, uint32_t depth,
67
uint32_t prune_level);
68
static uint32_t determine_search_depth(JOIN* join);
69
static int join_tab_cmp(const void* ptr1, const void* ptr2);
70
static int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
72
TODO: 'find_best' is here only temporarily until 'greedy_search' is
75
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index,
76
double record_count,double read_time);
77
static uint32_t cache_record_length(JOIN *join,uint32_t index);
78
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
79
static bool get_best_combination(JOIN *join);
80
static store_key *get_store_key(THD *thd,
81
KEYUSE *keyuse, table_map used_tables,
82
KEY_PART_INFO *key_part, unsigned char *key_buff,
84
static bool make_simple_join(JOIN *join,Table *tmp_table);
85
static void make_outerjoin_info(JOIN *join);
86
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
87
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
88
static bool only_eq_ref_tables(JOIN *join, order_st *order, table_map tables);
89
static void update_depend_map(JOIN *join);
90
static void update_depend_map(JOIN *join, order_st *order);
91
static order_st *remove_const(JOIN *join,order_st *first_order,COND *cond,
92
bool change_list, bool *simple_order);
93
static int return_zero_rows(JOIN *join, select_result *res,TableList *tables,
94
List<Item> &fields, bool send_row,
95
uint64_t select_options, const char *info,
97
static COND *build_equal_items(THD *thd, COND *cond,
80
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);
81
static COND *build_equal_items(Session *session, COND *cond,
98
82
COND_EQUAL *inherited,
99
83
List<TableList> *join_list,
100
84
COND_EQUAL **cond_equal_ref);
101
static COND* substitute_for_best_equal_field(COND *cond,
102
COND_EQUAL *cond_equal,
103
void *table_join_idx);
104
static COND *simplify_joins(JOIN *join, List<TableList> *join_list,
105
COND *conds, bool top, bool in_sj);
106
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
107
static void restore_prev_nj_state(JOIN_TAB *last);
108
static void reset_nj_counters(List<TableList> *join_list);
109
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
110
uint32_t first_unused);
113
void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);
114
static void restore_prev_sj_state(const table_map remaining_tables,
115
const JOIN_TAB *tab);
117
static COND *optimize_cond(JOIN *join, COND *conds,
118
List<TableList> *join_list,
119
Item::cond_result *cond_value);
120
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
121
static int do_select(JOIN *join,List<Item> *fields,Table *tmp_table);
123
static enum_nested_loop_state
124
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
126
static enum_nested_loop_state
127
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
128
static enum_nested_loop_state
129
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
130
static enum_nested_loop_state
131
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
132
static enum_nested_loop_state
133
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
134
static enum_nested_loop_state
135
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
136
static enum_nested_loop_state
137
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
139
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
140
static int join_read_system(JOIN_TAB *tab);
141
static int join_read_const(JOIN_TAB *tab);
142
static int join_read_key(JOIN_TAB *tab);
143
static int join_read_always_key(JOIN_TAB *tab);
144
static int join_read_last_key(JOIN_TAB *tab);
145
static int join_no_more_records(READ_RECORD *info);
146
static int join_read_next(READ_RECORD *info);
147
static int join_read_next_different(READ_RECORD *info);
148
static int join_init_quick_read_record(JOIN_TAB *tab);
149
static int test_if_quick_select(JOIN_TAB *tab);
150
static int join_init_read_record(JOIN_TAB *tab);
151
static int join_read_first(JOIN_TAB *tab);
152
static int join_read_next_same(READ_RECORD *info);
153
static int join_read_next_same_diff(READ_RECORD *info);
154
static int join_read_last(JOIN_TAB *tab);
155
static int join_read_prev_same(READ_RECORD *info);
156
static int join_read_prev(READ_RECORD *info);
157
int join_read_always_key_or_null(JOIN_TAB *tab);
158
int join_read_next_same_or_null(READ_RECORD *info);
159
static COND *make_cond_for_table(COND *cond,table_map table,
160
table_map used_table,
161
bool exclude_expensive_cond);
162
86
static Item* part_of_refkey(Table *form,Field *field);
163
static bool test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,
164
ha_rows select_limit, bool no_changes,
166
static bool list_contains_unique_index(Table *table,
167
bool (*find_func) (Field *, void *), void *data);
168
static bool find_field_in_item_list (Field *field, void *data);
169
static bool find_field_in_order_list (Field *field, void *data);
170
static int create_sort_index(THD *thd, JOIN *join, order_st *order,
171
ha_rows filesort_limit, ha_rows select_limit,
173
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields,
175
static int remove_dup_with_compare(THD *thd, Table *entry, Field **field,
176
ulong offset,Item *having);
177
static int remove_dup_with_hash_index(THD *thd,Table *table,
178
uint32_t field_count, Field **first_field,
87
static bool cmp_buffer_with_ref(JoinTable *tab);
88
static void change_cond_ref_to_const(Session *session,
89
vector<COND_CMP>& save_list,
94
static bool copy_blobs(Field **ptr);
180
ulong key_length,Item *having);
181
static int join_init_cache(THD *thd,JOIN_TAB *tables,uint32_t table_count);
182
static ulong used_blob_length(CACHE_FIELD **ptr);
183
static bool store_record_in_cache(JOIN_CACHE *cache);
184
static void reset_cache_read(JOIN_CACHE *cache);
185
static void reset_cache_write(JOIN_CACHE *cache);
186
static void read_cached_record(JOIN_TAB *tab);
187
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
188
static order_st *create_distinct_group(THD *thd, Item **ref_pointer_array,
189
order_st *order, List<Item> &fields,
190
List<Item> &all_fields,
191
bool *all_order_by_fields_used);
192
static bool test_if_subpart(order_st *a,order_st *b);
193
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
194
static void calc_group_buffer(JOIN *join,order_st *group);
195
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
196
static bool alloc_group_fields(JOIN *join,order_st *group);
197
// Create list for using with tempory table
198
static bool change_to_use_tmp_fields(THD *thd, Item **ref_pointer_array,
199
List<Item> &new_list1,
200
List<Item> &new_list2,
201
uint32_t elements, List<Item> &items);
202
// Create list for using with tempory table
203
static bool change_refs_to_tmp_fields(THD *thd, Item **ref_pointer_array,
204
List<Item> &new_list1,
205
List<Item> &new_list2,
206
uint32_t elements, List<Item> &items);
207
static void init_tmptable_sum_functions(Item_sum **func);
208
static void update_tmptable_sum_func(Item_sum **func,Table *tmp_table);
209
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
210
static bool add_ref_to_table_cond(THD *thd, JOIN_TAB *join_tab);
211
static bool setup_sum_funcs(THD *thd, Item_sum **func_ptr);
212
static bool init_sum_functions(Item_sum **func, Item_sum **end);
213
static bool update_sum_func(Item_sum **func);
214
void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
215
bool distinct, const char *message=NULL);
216
static Item *remove_additional_cond(Item* conds);
217
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
218
static bool test_if_ref(Item_field *left_item,Item *right_item);
219
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
220
Item *new_cond, bool fix_fields);
96
static bool eval_const_cond(COND *cond)
98
return ((Item_func*) cond)->val_int() ? true : false;
223
102
This is used to mark equalities that were made from i-th IN-equality.
382
265
ref->outer_ref= new_ref;
383
266
ref->ref= &ref->outer_ref;
385
if (!ref->fixed && ref->fix_fields(thd, 0))
268
if (!ref->fixed && ref->fix_fields(session, 0))
387
thd->used_tables|= item->used_tables();
270
session->used_tables|= item->used_tables();
392
#define MAGIC_IN_WHERE_TOP_LEVEL 10
394
Function to setup clauses without sum functions.
396
inline int setup_without_group(THD *thd, Item **ref_pointer_array,
400
List<Item> &all_fields,
403
order_st *group, bool *hidden_group_fields)
406
nesting_map save_allow_sum_func=thd->lex->allow_sum_func ;
408
thd->lex->allow_sum_func&= ~(1 << thd->lex->current_select->nest_level);
409
res= setup_conds(thd, tables, leaves, conds);
411
thd->lex->allow_sum_func|= 1 << thd->lex->current_select->nest_level;
412
res= res || setup_order(thd, ref_pointer_array, tables, fields, all_fields,
414
thd->lex->allow_sum_func&= ~(1 << thd->lex->current_select->nest_level);
415
res= res || setup_group(thd, ref_pointer_array, tables, fields, all_fields,
416
group, hidden_group_fields);
417
thd->lex->allow_sum_func= save_allow_sum_func;
421
275
/*****************************************************************************
422
276
Check fields, find best join, do the select and output fields.
423
277
mysql_select assumes that all tables are already opened
424
278
*****************************************************************************/
427
Prepare of whole select (including sub queries in future).
430
Add check of calculation of GROUP functions and fields:
431
SELECT COUNT(*)+table.col1 from table1;
439
JOIN::prepare(Item ***rref_pointer_array,
440
TableList *tables_init,
441
uint32_t wild_num, COND *conds_init, uint32_t og_num,
442
order_st *order_init, order_st *group_init,
444
order_st *proc_param_init, SELECT_LEX *select_lex_arg,
445
SELECT_LEX_UNIT *unit_arg)
447
// to prevent double initialization on EXPLAIN
453
group_list= group_init;
455
proc_param= proc_param_init;
456
tables_list= tables_init;
457
select_lex= select_lex_arg;
458
select_lex->join= this;
459
join_list= &select_lex->top_join_list;
460
union_part= unit_arg->is_union();
462
thd->lex->current_select->is_item_list_lookup= 1;
464
If we have already executed SELECT, then it have not sense to prevent
465
its table from update (see unique_table())
467
if (thd->derived_tables_processing)
468
select_lex->exclude_from_table_unique_test= true;
470
/* Check that all tables, fields, conds and order are ok */
472
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
473
setup_tables_and_check_access(thd, &select_lex->context, join_list,
474
tables_list, &select_lex->leaf_tables,
478
TableList *table_ptr;
479
for (table_ptr= select_lex->leaf_tables;
481
table_ptr= table_ptr->next_leaf)
484
if (setup_wild(thd, tables_list, fields_list, &all_fields, wild_num) ||
485
select_lex->setup_ref_array(thd, og_num) ||
486
setup_fields(thd, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
488
setup_without_group(thd, (*rref_pointer_array), tables_list,
489
select_lex->leaf_tables, fields_list,
490
all_fields, &conds, order, group_list,
491
&hidden_group_fields))
492
return(-1); /* purecov: inspected */
494
ref_pointer_array= *rref_pointer_array;
498
nesting_map save_allow_sum_func= thd->lex->allow_sum_func;
499
thd->where="having clause";
500
thd->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
501
select_lex->having_fix_field= 1;
502
bool having_fix_rc= (!having->fixed &&
503
(having->fix_fields(thd, &having) ||
504
having->check_cols(1)));
505
select_lex->having_fix_field= 0;
506
if (having_fix_rc || thd->is_error())
507
return(-1); /* purecov: inspected */
508
thd->lex->allow_sum_func= save_allow_sum_func;
512
Item_subselect *subselect;
513
Item_in_subselect *in_subs= NULL;
515
Are we in a subquery predicate?
516
TODO: the block below will be executed for every PS execution without need.
518
if ((subselect= select_lex->master_unit()->item))
520
bool do_semijoin= !test(thd->variables.optimizer_switch &
521
OPTIMIZER_SWITCH_NO_SEMIJOIN);
522
if (subselect->substype() == Item_subselect::IN_SUBS)
523
in_subs= (Item_in_subselect*)subselect;
526
Check if we're in subquery that is a candidate for flattening into a
527
semi-join (which is done done in flatten_subqueries()). The
529
1. Subquery predicate is an IN/=ANY subq predicate
530
2. Subquery is a single SELECT (not a UNION)
531
3. Subquery does not have GROUP BY or order_st BY
532
4. Subquery does not use aggregate functions or HAVING
533
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
534
6. No execution method was already chosen (by a prepared statement).
536
(*). We are not in a subquery of a single table UPDATE/DELETE that
537
doesn't have a JOIN (TODO: We should handle this at some
538
point by switching to multi-table UPDATE/DELETE)
540
(**). We're not in a confluent table-less subquery, like
544
!select_lex->master_unit()->first_select()->next_select() && // 2
545
!select_lex->group_list.elements && !order && // 3
546
!having && !select_lex->with_sum_func && // 4
547
thd->thd_marker && // 5
548
select_lex->outer_select()->join && // (*)
549
select_lex->master_unit()->first_select()->leaf_tables && // (**)
551
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
554
if (!in_subs->left_expr->fixed &&
555
in_subs->left_expr->fix_fields(thd, &in_subs->left_expr))
560
Check that the right part of the subselect contains no more than one
561
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
563
if (subselect->substype() == Item_subselect::IN_SUBS &&
564
(select_lex->item_list.elements !=
565
((Item_in_subselect*)subselect)->left_expr->cols()))
567
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
572
/* Register the subquery for further processing */
573
select_lex->outer_select()->join->sj_subselects.append(thd->mem_root, in_subs);
574
in_subs->expr_join_nest= (TableList*)thd->thd_marker;
578
bool do_materialize= !test(thd->variables.optimizer_switch &
579
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
581
Check if the subquery predicate can be executed via materialization.
582
The required conditions are:
583
1. Subquery predicate is an IN/=ANY subq predicate
584
2. Subquery is a single SELECT (not a UNION)
585
3. Subquery is not a table-less query. In this case there is no
586
point in materializing.
587
4. Subquery predicate is a top-level predicate
588
(this implies it is not negated)
589
TODO: this is a limitation that should be lifeted once we
590
implement correct NULL semantics (WL#3830)
591
5. Subquery is non-correlated
593
This is an overly restrictive condition. It can be extended to:
594
(Subquery is non-correlated ||
595
Subquery is correlated to any query outer to IN predicate ||
596
(Subquery is correlated to the immediate outer query &&
597
Subquery !contains {GROUP BY, order_st BY [LIMIT],
598
aggregate functions) && subquery predicate is not under "NOT IN"))
599
6. No execution method was already chosen (by a prepared statement).
601
(*) The subquery must be part of a SELECT statement. The current
602
condition also excludes multi-table update statements.
604
We have to determine whether we will perform subquery materialization
605
before calling the IN=>EXISTS transformation, so that we know whether to
606
perform the whole transformation or only that part of it which wraps
607
Item_in_subselect in an Item_in_optimizer.
609
if (do_materialize &&
611
!select_lex->master_unit()->first_select()->next_select() && // 2
612
select_lex->master_unit()->first_select()->leaf_tables && // 3
613
thd->lex->sql_command == SQLCOM_SELECT) // *
615
if (in_subs->is_top_level_item() && // 4
616
!in_subs->is_correlated && // 5
617
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
618
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
621
Item_subselect::trans_res trans_res;
622
if ((trans_res= subselect->select_transformer(this)) !=
623
Item_subselect::RES_OK)
625
return((trans_res == Item_subselect::RES_ERROR));
634
for (ord= order; ord; ord= ord->next)
636
Item *item= *ord->item;
637
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
638
item->split_sum_func(thd, ref_pointer_array, all_fields);
642
if (having && having->with_sum_func)
643
having->split_sum_func2(thd, ref_pointer_array, all_fields,
645
if (select_lex->inner_sum_func_list)
647
Item_sum *end=select_lex->inner_sum_func_list;
648
Item_sum *item_sum= end;
651
item_sum= item_sum->next;
652
item_sum->split_sum_func2(thd, ref_pointer_array,
653
all_fields, item_sum->ref_by, false);
654
} while (item_sum != end);
657
if (select_lex->inner_refs_list.elements &&
658
fix_inner_refs(thd, all_fields, select_lex, ref_pointer_array))
662
Check if there are references to un-aggregated columns when computing
663
aggregate functions with implicit grouping (there is no GROUP BY).
665
MODE_ONLY_FULL_GROUP_BY is enabled here by default
667
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
669
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
670
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
674
/* Caclulate the number of groups */
676
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
681
goto err; /* purecov: inspected */
683
if (result && result->prepare(fields_list, unit_arg))
684
goto err; /* purecov: inspected */
686
/* Init join struct */
687
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
688
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
689
this->group= group_list != 0;
692
#ifdef RESTRICTED_GROUP
693
if (sum_func_count && !group_list && (func_count || field_count))
695
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
699
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
701
if (alloc_func_list())
707
return(-1); /* purecov: inspected */
712
Remove the predicates pushed down into the subquery
715
JOIN::remove_subq_pushed_predicates()
716
where IN Must be NULL
717
OUT The remaining WHERE condition, or NULL
720
Given that this join will be executed using (unique|index)_subquery,
721
without "checking NULL", remove the predicates that were pushed down
724
If the subquery compares scalar values, we can remove the condition that
725
was wrapped into trig_cond (it will be checked when needed by the subquery
728
If the subquery compares row values, we need to keep the wrapped
729
equalities in the WHERE clause: when the left (outer) tuple has both NULL
730
and non-NULL values, we'll do a full table scan and will rely on the
731
equalities corresponding to non-NULL parts of left tuple to filter out
732
non-matching records.
734
TODO: We can remove the equalities that will be guaranteed to be true by the
735
fact that subquery engine will be using index lookup. This must be done only
736
for cases where there are no conversion errors of significance, e.g. 257
737
that is searched in a byte. But this requires homogenization of the return
738
codes of all Field*::store() methods.
741
void JOIN::remove_subq_pushed_predicates(Item **where)
743
if (conds->type() == Item::FUNC_ITEM &&
744
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
745
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
746
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
747
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
748
((Item_func *)conds)->arguments()[0]))
757
281
Index lookup-based subquery: save some flags for EXPLAIN output
796
Check if the table's rowid is included in the temptable
799
sj_table_is_included()
801
join_tab The table to be checked
804
SemiJoinDuplicateElimination: check the table's rowid should be included
805
in the temptable. This is so if
807
1. The table is not embedded within some semi-join nest
808
2. The has been pulled out of a semi-join nest, or
810
3. The table is functionally dependent on some previous table
812
[4. This is also true for constant tables that can't be
813
NULL-complemented but this function is not called for such tables]
816
true - Include table's rowid
820
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
822
if (join_tab->emb_sj_nest)
825
/* Check if this table is functionally dependent on the tables that
826
are within the same outer join nest
828
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
829
if (join_tab->type == JT_EQ_REF)
831
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
833
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
835
JOIN_TAB *ref_tab= join->join_tab + idx;
836
if (embedding == ref_tab->table->pos_in_table_list->embedding)
839
/* Ok, functionally dependent */
842
/* Not functionally dependent => need to include*/
848
Setup the strategies to eliminate semi-join duplicates.
851
setup_semijoin_dups_elimination()
853
options Join options (needed to see if join buffering will be
855
no_jbuf_after Another bit of information re where join buffering will
859
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
862
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
864
2. FirstMatch (pick only the 1st matching row combination of inner tables)
865
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
866
together and picking the 1st one)
868
The join order has "duplicate-generating ranges", and every range is
869
served by one strategy or a combination of FirstMatch with with some
872
"Duplicate-generating range" is defined as a range within the join order
873
that contains all of the inner tables of a semi-join. All ranges must be
874
disjoint, if tables of several semi-joins are interleaved, then the ranges
875
are joined together, which is equivalent to converting
876
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
878
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
881
Applicability conditions are as follows:
883
DuplicateWeedout strategy
884
~~~~~~~~~~~~~~~~~~~~~~~~~
886
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
887
+------+ +=========================+ +---+
890
(1) - Prefix of OuterTables (those that participate in
891
IN-equality and/or are correlated with subquery) and outer
892
Noncorrelated Tables.
893
(2) - The handled range. The range starts with the first sj-inner
894
table, and covers all sj-inner and outer tables
895
Within the range, Inner, Outer, outer Noncorrelated tables
896
may follow in any order.
897
(3) - The suffix of outer Noncorrelated tables.
902
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
903
+------+ +==================+ +---+
906
(1) - Prefix of outer and non-correlated tables
907
(2) - The handled range, which may contain only inner and
908
non-correlated tables.
909
(3) - The suffix of outer Noncorrelated tables.
914
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
915
+--------+ +===========+ +=============+ +------+
918
(1) - Prefix that may contain any outer tables. The prefix must contain
919
all the non-trivially correlated outer tables. (non-trivially means
920
that the correlation is not just through the IN-equality).
922
(2) - Inner table for which the InsideOut scan is performed.
924
(3) - The remainder of the duplicate-generating range. It is served by
925
application of FirstMatch strategy, with the exception that
926
outer IN-correlated tables are considered to be non-correlated.
928
(4) - THe suffix of outer and outer non-correlated tables.
930
If several strategies are applicable, their relative priorities are:
935
This function walks over the join order and sets up the strategies by
936
setting appropriate members in join_tab structures.
940
true Out of memory error
944
int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
946
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
949
0 - invalid (EOF marker),
951
2 - Temptable (maybe confluent),
952
3 - Temptable with join buffering
955
uint32_t start_idx; /* Left range bound */
956
uint32_t end_idx; /* Right range bound */
958
For Temptable strategy: Bitmap of all outer and correlated tables from
959
all involved join nests.
961
table_map outer_tables;
962
} dups_ranges [MAX_TABLES];
964
TableList *emb_insideout_nest= NULL;
965
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
966
tables) whose ranges we're in */
967
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
968
table_map range_start_map= 0; /* table_map at current range start */
969
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
974
First pass: locate the duplicate-generating ranges and pick the strategies.
976
for (i=join->const_tables ; i < join->tables ; i++)
978
JOIN_TAB *tab=join->join_tab+i;
979
Table *table=tab->table;
980
cur_map |= table->map;
982
if (tab->emb_sj_nest) // Encountered an sj-inner table
986
dups_ranges[cur_range].start_idx= i;
987
range_start_map= cur_map & ~table->map;
989
Remember if this is a possible start of range that is covered by
990
the InsideOut strategy (the reason that it is not covered could
991
be that it overlaps with anther semi-join's range. we don't
992
support InsideOut for joined ranges)
994
if (join->best_positions[i].use_insideout_scan)
995
emb_insideout_nest= tab->emb_sj_nest;
998
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
999
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
1001
if (tab->emb_sj_nest != emb_insideout_nest)
1004
Two different semi-joins interleave. This cannot be handled by
1007
emb_insideout_nest= NULL;
1011
if (emb_sj_map) /* We're in duplicate-generating range */
1013
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
1014
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
1015
i <= no_jbuf_after && !dealing_with_jbuf)
1018
This table uses join buffering, which makes use of FirstMatch or
1019
InsideOut strategies impossible for the current and (we assume)
1020
preceding duplicate-producing ranges.
1021
That is, for the join order:
1023
x x [ x x] x [x x x] x [x x X* x] x
1025
+-----+ +-----+ | join buffering use
1028
we'll have to remove r1 and r2 and use duplicate-elimination
1029
strategy that spans all the tables, starting from the very 1st
1032
dealing_with_jbuf= true;
1033
emb_insideout_nest= false;
1036
Absorb all preceding duplicate-eliminating ranges. Their strategies
1039
for (int prev_range= 0; prev_range < cur_range; prev_range++)
1041
dups_ranges[cur_range].outer_tables |=
1042
dups_ranges[prev_range].outer_tables;
1044
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
1045
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
1050
Check if we are at the end of duplicate-producing range. We are if
1052
1. It's an InsideOut range (which presumes all correlated tables are
1053
in the prefix), and all inner tables are in the join order prefix,
1055
2. It's a DuplicateElimination range (possibly covering several
1056
SJ-nests), and all inner, outer, and correlated tables of all
1057
sj-nests are in the join order prefix.
1059
bool end_of_range= false;
1060
if (emb_insideout_nest &&
1061
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
1063
/* Save that this range is handled with InsideOut: */
1064
dups_ranges[cur_range].strategy= 1;
1067
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
1070
This is a complete range to be handled with either DuplicateWeedout
1073
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
1075
This will hold tables from within the range that need to be put
1076
into the join buffer before we can use the FirstMatch on its tail.
1078
dups_ranges[cur_range].outer_tables= emb_outer_tables &
1085
dups_ranges[cur_range].end_idx= i+1;
1086
emb_sj_map= emb_outer_tables= 0;
1087
emb_insideout_nest= NULL;
1088
dealing_with_jbuf= false;
1089
dups_ranges[++cur_range].strategy= 0;
1094
THD *thd= join->thd;
1095
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
1097
Second pass: setup the chosen strategies
1099
for (int j= 0; j < cur_range; j++)
1101
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
1103
if (dups_ranges[j].strategy == 1) // InsideOut strategy
1105
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
1108
else // DuplicateWeedout strategy
1110
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
1111
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
1112
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
1113
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
1114
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
1115
uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
1116
JOIN_TAB *last_outer_tab= tab - 1;
1118
Walk through the range and remember
1119
- tables that need their rowids to be put into temptable
1120
- the last outer table
1122
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1124
if (sj_table_is_included(join, tab))
1126
last_tab->join_tab= tab;
1127
last_tab->rowid_offset= jt_rowid_offset;
1128
jt_rowid_offset += tab->table->file->ref_length;
1129
if (tab->table->maybe_null)
1131
last_tab->null_byte= jt_null_bits / 8;
1132
last_tab->null_bit= jt_null_bits++;
1135
tab->table->prepare_for_position();
1136
tab->rowid_keep_flags= rowid_keep_flags;
1138
cur_map |= tab->table->map;
1139
if (!tab->emb_sj_nest && bitmap_covers(cur_map,
1140
dups_ranges[j].outer_tables))
1141
last_outer_tab= tab;
1144
if (jt_rowid_offset) /* Temptable has at least one rowid */
1146
SJ_TMP_TABLE *sjtbl;
1147
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
1148
if (!(sjtbl= (SJ_TMP_TABLE*)thd->alloc(sizeof(SJ_TMP_TABLE))) ||
1149
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) thd->alloc(tabs_size)))
1151
memcpy(sjtbl->tabs, sjtabs, tabs_size);
1152
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
1153
sjtbl->rowid_len= jt_rowid_offset;
1154
sjtbl->null_bits= jt_null_bits;
1155
sjtbl->null_bytes= (jt_null_bits + 7)/8;
1157
*next_sjtbl_ptr= sjtbl;
1158
next_sjtbl_ptr= &(sjtbl->next);
1162
create_duplicate_weedout_tmp_table(thd,
1167
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
1168
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
1170
tab= last_outer_tab + 1;
1171
jump_to= last_outer_tab;
1174
/* Create the FirstMatch tail */
1175
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1177
if (tab->emb_sj_nest)
1178
tab->do_firstmatch= jump_to;
1187
static void cleanup_sj_tmp_tables(JOIN *join)
1189
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
1190
sj_tbl= sj_tbl->next)
1192
if (sj_tbl->tmp_table)
1194
sj_tbl->tmp_table->free_tmp_table(join->thd);
1197
join->sj_tmp_tables= NULL;
1200
uint32_t make_join_orderinfo(JOIN *join);
1203
global select optimisation.
1206
error code saved in field 'error'
1217
// to prevent double initialization on EXPLAIN
1222
thd_proc_info(thd, "optimizing");
1223
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
1224
unit->select_limit_cnt);
1225
/* select_limit is used to decide if we are likely to scan the whole table */
1226
select_limit= unit->select_limit_cnt;
1227
if (having || (select_options & OPTION_FOUND_ROWS))
1228
select_limit= HA_POS_ERROR;
1229
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
1230
// Ignore errors of execution if option IGNORE present
1231
if (thd->lex->ignore)
1232
thd->lex->current_select->no_error= 1;
1234
#ifdef HAVE_REF_TO_FIELDS // Not done yet
1235
/* Add HAVING to WHERE if possible */
1236
if (having && !group_list && !sum_func_count)
1243
else if ((conds=new Item_cond_and(conds,having)))
1246
Item_cond_and can't be fixed after creation, so we do not check
1249
conds->fix_fields(thd, &conds);
1250
conds->change_ref_to_fields(thd, tables_list);
1251
conds->top_level_item();
1257
/* Convert all outer joins to inner joins if possible */
1258
conds= simplify_joins(this, join_list, conds, true, false);
1259
build_bitmap_for_nested_joins(join_list, 0);
1261
conds= optimize_cond(this, conds, join_list, &cond_value);
1262
if (thd->is_error())
1269
having= optimize_cond(this, having, join_list, &having_value);
1270
if (thd->is_error())
1275
if (select_lex->where)
1276
select_lex->cond_value= cond_value;
1277
if (select_lex->having)
1278
select_lex->having_value= having_value;
1280
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
1281
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
1282
{ /* Impossible cond */
1283
zero_result_cause= having_value == Item::COND_FALSE ?
1284
"Impossible HAVING" : "Impossible WHERE";
1290
/* Optimize count(*), cmin() and cmax() */
1291
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
1295
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
1296
to the WHERE conditions,
1297
or 1 if all items were resolved,
1298
or 0, or an error number HA_ERR_...
1300
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
1302
if (res == HA_ERR_KEY_NOT_FOUND)
1304
zero_result_cause= "No matching min/max row";
1315
zero_result_cause= "No matching min/max row";
1319
zero_result_cause= "Select tables optimized away";
1320
tables_list= 0; // All tables resolved
1322
Extract all table-independent conditions and replace the WHERE
1323
clause with them. All other conditions were computed by opt_sum_query
1324
and the MIN/MAX/COUNT function(s) have been replaced by constants,
1325
so there is no need to compute the whole WHERE clause again.
1326
Notice that make_cond_for_table() will always succeed to remove all
1327
computed conditions, because opt_sum_query() is applicable only to
1329
Preserve conditions for EXPLAIN.
1331
if (conds && !(thd->lex->describe & DESCRIBE_EXTENDED))
1333
COND *table_independent_conds=
1334
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
1335
conds= table_independent_conds;
1344
error= -1; // Error is sent to client
1345
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
1347
/* Calculate how to do the join */
1348
thd_proc_info(thd, "statistics");
1349
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
1350
thd->is_fatal_error)
1355
/* Remove distinct if only const tables */
1356
select_distinct= select_distinct && (const_tables != tables);
1357
thd_proc_info(thd, "preparing");
1358
if (result->initialize_tables(this))
1360
return(1); // error == -1
1362
if (const_table_map != found_const_table_map &&
1363
!(select_options & SELECT_DESCRIBE) &&
1365
!(conds->used_tables() & RAND_TABLE_BIT) ||
1366
select_lex->master_unit() == &thd->lex->unit)) // upper level SELECT
1368
zero_result_cause= "no matching row in const table";
1372
if (!(thd->options & OPTION_BIG_SELECTS) &&
1373
best_read > (double) thd->variables.max_join_size &&
1374
!(select_options & SELECT_DESCRIBE))
1375
{ /* purecov: inspected */
1376
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
1380
if (const_tables && !thd->locked_tables &&
1381
!(select_options & SELECT_NO_UNLOCK))
1382
mysql_unlock_some_tables(thd, table, const_tables);
1383
if (!conds && outer_join)
1385
/* Handle the case where we have an OUTER JOIN without a WHERE */
1386
conds=new Item_int((int64_t) 1,1); // Always true
1388
select= make_select(*table, const_table_map,
1389
const_table_map, conds, 1, &error);
1391
{ /* purecov: inspected */
1392
error= -1; /* purecov: inspected */
1396
reset_nj_counters(join_list);
1397
make_outerjoin_info(this);
1400
Among the equal fields belonging to the same multiple equality
1401
choose the one that is to be retrieved first and substitute
1402
all references to these in where condition for a reference for
1407
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
1408
conds->update_used_tables();
1412
Permorm the the optimization on fields evaluation mentioned above
1413
for all on expressions.
1415
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
1417
if (*tab->on_expr_ref)
1419
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
1422
(*tab->on_expr_ref)->update_used_tables();
1426
if (conds &&!outer_join && const_table_map != found_const_table_map &&
1427
(select_options & SELECT_DESCRIBE) &&
1428
select_lex->master_unit() == &thd->lex->unit) // upper level SELECT
1430
conds=new Item_int((int64_t) 0,1); // Always false
1432
if (make_join_select(this, select, conds))
1435
"Impossible WHERE noticed after reading const tables";
1436
return(0); // error == 0
1439
error= -1; /* if goto err */
1441
/* Optimize distinct away if possible */
1443
order_st *org_order= order;
1444
order=remove_const(this, order,conds,1, &simple_order);
1445
if (thd->is_error())
1452
If we are using order_st BY NULL or order_st BY const_expression,
1453
return result in any order (even if we are using a GROUP BY)
1455
if (!order && org_order)
1459
Check if we can optimize away GROUP BY/DISTINCT.
1460
We can do that if there are no aggregate functions, the
1461
fields in DISTINCT clause (if present) and/or columns in GROUP BY
1462
(if present) contain direct references to all key parts of
1463
an unique index (in whatever order) and if the key parts of the
1464
unique index cannot contain NULLs.
1465
Note that the unique keys for DISTINCT and GROUP BY should not
1466
be the same (as long as they are unique).
1468
The FROM clause must contain a single non-constant table.
1470
if (tables - const_tables == 1 && (group_list || select_distinct) &&
1471
!tmp_table_param.sum_func_count &&
1472
(!join_tab[const_tables].select ||
1473
!join_tab[const_tables].select->quick ||
1474
join_tab[const_tables].select->quick->get_type() !=
1475
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
1478
list_contains_unique_index(join_tab[const_tables].table,
1479
find_field_in_order_list,
1480
(void *) group_list))
1483
We have found that grouping can be removed since groups correspond to
1484
only one row anyway, but we still have to guarantee correct result
1485
order. The line below effectively rewrites the query from GROUP BY
1486
<fields> to order_st BY <fields>. There are two exceptions:
1487
- if skip_sort_order is set (see above), then we can simply skip
1489
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
1490
with the GROUP BY ones, i.e. either one is a prefix of another.
1491
We only check if the order_st BY is a prefix of GROUP BY. In this case
1492
test_if_subpart() copies the ASC/DESC attributes from the original
1494
If GROUP BY is a prefix of order_st BY, then it is safe to leave
1497
if (!order || test_if_subpart(group_list, order))
1498
order= skip_sort_order ? 0 : group_list;
1500
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
1501
rewritten to IGNORE INDEX FOR order_st BY(fields).
1503
join_tab->table->keys_in_use_for_order_by=
1504
join_tab->table->keys_in_use_for_group_by;
1508
if (select_distinct &&
1509
list_contains_unique_index(join_tab[const_tables].table,
1510
find_field_in_item_list,
1511
(void *) &fields_list))
1516
if (group_list || tmp_table_param.sum_func_count)
1518
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
1521
else if (select_distinct && tables - const_tables == 1)
1524
We are only using one table. In this case we change DISTINCT to a
1526
- The GROUP BY can be done through indexes (no sort) and the order_st
1527
BY only uses selected fields.
1528
(In this case we can later optimize away GROUP BY and order_st BY)
1529
- We are scanning the whole table without LIMIT
1531
- We are using CALC_FOUND_ROWS
1532
- We are using an order_st BY that can't be optimized away.
1534
We don't want to use this optimization when we are using LIMIT
1535
because in this case we can just create a temporary table that
1536
holds LIMIT rows and stop when this table is full.
1538
JOIN_TAB *tab= &join_tab[const_tables];
1539
bool all_order_fields_used;
1541
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
1542
&tab->table->keys_in_use_for_order_by);
1543
if ((group_list=create_distinct_group(thd, select_lex->ref_pointer_array,
1544
order, fields_list, all_fields,
1545
&all_order_fields_used)))
1547
bool skip_group= (skip_sort_order &&
1548
test_if_skip_sort_order(tab, group_list, select_limit, 1,
1549
&tab->table->keys_in_use_for_group_by) != 0);
1550
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
1551
if ((skip_group && all_order_fields_used) ||
1552
select_limit == HA_POS_ERROR ||
1553
(order && !skip_sort_order))
1555
/* Change DISTINCT to GROUP BY */
1558
if (all_order_fields_used)
1560
if (order && skip_sort_order)
1563
Force MySQL to read the table in sorted order to get result in
1566
tmp_table_param.quick_group=0;
1570
group=1; // For end_write_group
1575
else if (thd->is_fatal_error) // End of memory
1580
order_st *old_group_list;
1581
group_list= remove_const(this, (old_group_list= group_list), conds,
1582
rollup.state == ROLLUP::STATE_NONE,
1584
if (thd->is_error())
1589
if (old_group_list && !group_list)
1592
if (!group_list && group)
1594
order=0; // The output has only one row
1596
select_distinct= 0; // No need in distinct for 1 row
1597
group_optimized_away= 1;
1600
calc_group_buffer(this, group_list);
1601
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
1603
if (test_if_subpart(group_list, order) ||
1604
(!group_list && tmp_table_param.sum_func_count))
1607
// Can't use sort on head table if using row cache
1617
Check if we need to create a temporary table.
1618
This has to be done if all tables are not already read (const tables)
1619
and one of the following conditions holds:
1620
- We are using DISTINCT (simple distinct's are already optimized away)
1621
- We are using an order_st BY or GROUP BY on fields not in the first table
1622
- We are using different order_st BY and GROUP BY orders
1623
- The user wants us to buffer the result.
1625
need_tmp= (const_tables != tables &&
1626
((select_distinct || !simple_order || !simple_group) ||
1627
(group_list && order) ||
1628
test(select_options & OPTION_BUFFER_RESULT)));
1630
uint32_t no_jbuf_after= make_join_orderinfo(this);
1631
uint64_t select_opts_for_readinfo=
1632
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
1634
sj_tmp_tables= NULL;
1635
if (!select_lex->sj_nests.is_empty())
1636
setup_semijoin_dups_elimination(this, select_opts_for_readinfo,
1639
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1640
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1643
/* Create all structures needed for materialized subquery execution. */
1644
if (setup_subquery_materialization())
1648
is this simple IN subquery?
1650
if (!group_list && !order &&
1651
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1652
tables == 1 && conds &&
1658
if (join_tab[0].type == JT_EQ_REF &&
1659
join_tab[0].ref.items[0]->name == in_left_expr_name)
1661
remove_subq_pushed_predicates(&where);
1662
save_index_subquery_explain_info(join_tab, where);
1663
join_tab[0].type= JT_UNIQUE_SUBQUERY;
1667
subselect_uniquesubquery_engine(thd,
1672
else if (join_tab[0].type == JT_REF &&
1673
join_tab[0].ref.items[0]->name == in_left_expr_name)
1675
remove_subq_pushed_predicates(&where);
1676
save_index_subquery_explain_info(join_tab, where);
1677
join_tab[0].type= JT_INDEX_SUBQUERY;
1681
subselect_indexsubquery_engine(thd,
1688
} else if (join_tab[0].type == JT_REF_OR_NULL &&
1689
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1690
having->name == in_having_cond)
1692
join_tab[0].type= JT_INDEX_SUBQUERY;
1694
conds= remove_additional_cond(conds);
1695
save_index_subquery_explain_info(join_tab, conds);
1697
change_engine(new subselect_indexsubquery_engine(thd,
1707
Need to tell handlers that to play it safe, it should fetch all
1708
columns of the primary key of the tables: this is because MySQL may
1709
build row pointers for the rows, and for all columns of the primary key
1710
the read set has not necessarily been set by the server code.
1712
if (need_tmp || select_distinct || group_list || order)
1714
for (uint32_t i = const_tables; i < tables; i++)
1715
join_tab[i].table->prepare_for_position();
1718
if (const_tables != tables)
1721
Because filesort always does a full table scan or a quick range scan
1722
we must add the removed reference to the select for the table.
1723
We only need to do this when we have a simple_order or simple_group
1724
as in other cases the join is done before the sort.
1726
if ((order || group_list) &&
1727
(join_tab[const_tables].type != JT_ALL) &&
1728
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
1729
((order && simple_order) || (group_list && simple_group)))
1731
if (add_ref_to_table_cond(thd,&join_tab[const_tables])) {
1736
if (!(select_options & SELECT_BIG_RESULT) &&
1739
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1740
unit->select_limit_cnt, 0,
1741
&join_tab[const_tables].table->
1742
keys_in_use_for_group_by))) ||
1744
tmp_table_param.quick_group)
1746
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1751
Force using of tmp table if sorting by a SP or UDF function due to
1752
their expensive and probably non-deterministic nature.
1754
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1756
Item *item= *tmp_order->item;
1757
if (item->is_expensive())
1759
/* Force tmp table without sort */
1760
need_tmp=1; simple_order=simple_group=0;
1768
if (select_options & SELECT_DESCRIBE)
1776
The loose index scan access method guarantees that all grouping or
1777
duplicate row elimination (for distinct) is already performed
1778
during data retrieval, and that all MIN/MAX functions are already
1779
computed for each group. Thus all MIN/MAX functions should be
1780
treated as regular functions, and there is no need to perform
1781
grouping in the main execution loop.
1782
Notice that currently loose index scan is applicable only for
1783
single table queries, thus it is sufficient to test only the first
1784
join_tab element of the plan for its access method.
1786
if (join_tab->is_using_loose_index_scan())
1787
tmp_table_param.precomputed_group_by= true;
1789
/* Create a tmp table if distinct or if the sort is too complicated */
1792
thd_proc_info(thd, "Creating tmp table");
1794
init_items_ref_array();
1796
tmp_table_param.hidden_field_count= (all_fields.elements -
1797
fields_list.elements);
1798
order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1801
Pushing LIMIT to the temporary table creation is not applicable
1802
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1803
there are aggregate functions, because in all these cases we need
1806
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1808
!thd->lex->current_select->with_sum_func) ?
1809
select_limit : HA_POS_ERROR;
1811
if (!(exec_tmp_table1=
1812
create_tmp_table(thd, &tmp_table_param, all_fields,
1814
group_list ? 0 : select_distinct,
1815
group_list && simple_group,
1824
We don't have to store rows in temp table that doesn't match HAVING if:
1825
- we are sorting the table and writing complete group rows to the
1827
- We are using DISTINCT without resolving the distinct as a GROUP BY
1830
If having is not handled here, it will be checked before the row
1831
is sent to the client.
1834
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1837
/* if group or order on first table, sort first */
1838
if (group_list && simple_group)
1840
thd_proc_info(thd, "Sorting for group");
1841
if (create_sort_index(thd, this, group_list,
1842
HA_POS_ERROR, HA_POS_ERROR, false) ||
1843
alloc_group_fields(this, group_list) ||
1844
make_sum_func_list(all_fields, fields_list, 1) ||
1845
setup_sum_funcs(thd, sum_funcs))
1853
if (make_sum_func_list(all_fields, fields_list, 0) ||
1854
setup_sum_funcs(thd, sum_funcs))
1859
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1861
thd_proc_info(thd, "Sorting for order");
1862
if (create_sort_index(thd, this, order,
1863
HA_POS_ERROR, HA_POS_ERROR, true))
1872
Optimize distinct when used on some of the tables
1873
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1874
In this case we can stop scanning t2 when we have found one t1.a
1877
if (exec_tmp_table1->distinct)
1879
table_map used_tables= thd->used_tables;
1880
JOIN_TAB *last_join_tab= join_tab+tables-1;
1883
if (used_tables & last_join_tab->table->map)
1885
last_join_tab->not_used_in_distinct=1;
1886
} while (last_join_tab-- != join_tab);
1887
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1888
if (order && skip_sort_order)
1890
/* Should always succeed */
1891
if (test_if_skip_sort_order(&join_tab[const_tables],
1892
order, unit->select_limit_cnt, 0,
1893
&join_tab[const_tables].table->
1894
keys_in_use_for_order_by))
1900
If this join belongs to an uncacheable subquery save
1903
if (select_lex->uncacheable && !is_top_level_join() &&
1904
init_save_join_tab())
1905
return(-1); /* purecov: inspected */
1914
Restore values in temporary join.
1916
void JOIN::restore_tmp()
1918
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1925
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1926
select_lex->offset_limit->val_uint() :
1931
if (exec_tmp_table1)
1933
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1934
exec_tmp_table1->file->ha_delete_all_rows();
1935
free_io_cache(exec_tmp_table1);
1936
filesort_free_buffers(exec_tmp_table1,0);
1938
if (exec_tmp_table2)
1940
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1941
exec_tmp_table2->file->ha_delete_all_rows();
1942
free_io_cache(exec_tmp_table2);
1943
filesort_free_buffers(exec_tmp_table2,0);
1946
set_items_ref_array(items0);
1949
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1954
/* Reset of sum functions */
1957
Item_sum *func, **func_ptr= sum_funcs;
1958
while ((func= *(func_ptr++)))
1966
@brief Save the original join layout
1968
@details Saves the original join layout so it can be reused in
1969
re-execution and for EXPLAIN.
1971
@return Operation status
1973
@retval 1 error occurred.
1977
JOIN::init_save_join_tab()
1979
if (!(tmp_join= (JOIN*)thd->alloc(sizeof(JOIN))))
1980
return 1; /* purecov: inspected */
1981
error= 0; // Ensure that tmp_join.error= 0
1988
JOIN::save_join_tab()
1990
if (!join_tab_save && select_lex->master_unit()->uncacheable)
1992
if (!(join_tab_save= (JOIN_TAB*)thd->memdup((unsigned char*) join_tab,
1993
sizeof(JOIN_TAB) * tables)))
2004
Note, that create_sort_index calls test_if_skip_sort_order and may
2005
finally replace sorting with index scan if there is a LIMIT clause in
2006
the query. It's never shown in EXPLAIN!
2009
When can we have here thd->net.report_error not zero?
2014
List<Item> *columns_list= &fields_list;
2017
thd_proc_info(thd, "executing");
2019
(void) result->prepare2(); // Currently, this cannot fail.
2021
if (!tables_list && (tables || !select_lex->with_sum_func))
2022
{ // Only test of functions
2023
if (select_options & SELECT_DESCRIBE)
2024
select_describe(this, false, false, false,
2025
(zero_result_cause?zero_result_cause:"No tables used"));
2028
result->send_fields(*columns_list,
2029
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2031
We have to test for 'conds' here as the WHERE may not be constant
2032
even if we don't have any tables for prepared statements or if
2033
conds uses something like 'rand()'.
2035
if (cond_value != Item::COND_FALSE &&
2036
(!conds || conds->val_int()) &&
2037
(!having || having->val_int()))
2039
if (do_send_rows && result->send_data(fields_list))
2043
error= (int) result->send_eof();
2044
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 :
2045
thd->sent_row_count);
2050
error=(int) result->send_eof();
2054
/* Single select (without union) always returns 0 or 1 row */
2055
thd->limit_found_rows= send_records;
2056
thd->examined_row_count= 0;
2060
Don't reset the found rows count if there're no tables as
2061
FOUND_ROWS() may be called. Never reset the examined row count here.
2062
It must be accumulated from all join iterations of all join parts.
2065
thd->limit_found_rows= 0;
2067
if (zero_result_cause)
2069
(void) return_zero_rows(this, result, select_lex->leaf_tables,
2071
send_row_on_empty_set(),
2078
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) &&
2079
get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
2082
if (select_options & SELECT_DESCRIBE)
2085
Check if we managed to optimize order_st BY away and don't use temporary
2086
table to resolve order_st BY: in that case, we only may need to do
2087
filesort for GROUP BY.
2089
if (!order && !no_order && (!skip_sort_order || !need_tmp))
2092
Reset 'order' to 'group_list' and reinit variables describing
2096
simple_order= simple_group;
2100
(order != group_list || !(select_options & SELECT_BIG_RESULT)) &&
2101
(const_tables == tables ||
2102
((simple_order || skip_sort_order) &&
2103
test_if_skip_sort_order(&join_tab[const_tables], order,
2105
&join_tab[const_tables].table->
2106
keys_in_use_for_query))))
2109
select_describe(this, need_tmp,
2110
order != 0 && !skip_sort_order,
2112
!tables ? "No tables used" : NULL);
2116
JOIN *curr_join= this;
2117
List<Item> *curr_all_fields= &all_fields;
2118
List<Item> *curr_fields_list= &fields_list;
2119
Table *curr_tmp_table= 0;
2121
Initialize examined rows here because the values from all join parts
2122
must be accumulated in examined_row_count. Hence every join
2123
iteration must count from zero.
2125
curr_join->examined_rows= 0;
2127
/* Create a tmp table if distinct or if the sort is too complicated */
2133
We are in a non cacheable sub query. Get the saved join structure
2135
(curr_join may have been modified during last exection and we need
2138
curr_join= tmp_join;
2140
curr_tmp_table= exec_tmp_table1;
2142
/* Copy data to the temporary table */
2143
thd_proc_info(thd, "Copying to tmp table");
2144
if (!curr_join->sort_and_group &&
2145
curr_join->const_tables != curr_join->tables)
2146
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2147
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2152
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
2154
if (curr_join->having)
2155
curr_join->having= curr_join->tmp_having= 0; // Allready done
2157
/* Change sum_fields reference to calculated fields in tmp_table */
2158
curr_join->all_fields= *curr_all_fields;
2161
items1= items0 + all_fields.elements;
2162
if (sort_and_group || curr_tmp_table->group)
2164
if (change_to_use_tmp_fields(thd, items1,
2165
tmp_fields_list1, tmp_all_fields1,
2166
fields_list.elements, all_fields))
2171
if (change_refs_to_tmp_fields(thd, items1,
2172
tmp_fields_list1, tmp_all_fields1,
2173
fields_list.elements, all_fields))
2176
curr_join->tmp_all_fields1= tmp_all_fields1;
2177
curr_join->tmp_fields_list1= tmp_fields_list1;
2178
curr_join->items1= items1;
2180
curr_all_fields= &tmp_all_fields1;
2181
curr_fields_list= &tmp_fields_list1;
2182
curr_join->set_items_ref_array(items1);
2184
if (sort_and_group || curr_tmp_table->group)
2186
curr_join->tmp_table_param.field_count+=
2187
curr_join->tmp_table_param.sum_func_count+
2188
curr_join->tmp_table_param.func_count;
2189
curr_join->tmp_table_param.sum_func_count=
2190
curr_join->tmp_table_param.func_count= 0;
2194
curr_join->tmp_table_param.field_count+=
2195
curr_join->tmp_table_param.func_count;
2196
curr_join->tmp_table_param.func_count= 0;
2199
if (curr_tmp_table->group)
2200
{ // Already grouped
2201
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
2202
curr_join->order= curr_join->group_list; /* order by group */
2203
curr_join->group_list= 0;
2207
If we have different sort & group then we must sort the data by group
2208
and copy it to another tmp table
2209
This code is also used if we are using distinct something
2210
we haven't been able to store in the temporary table yet
2211
like SEC_TO_TIME(SUM(...)).
2214
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))
2215
{ /* Must copy to another table */
2216
/* Free first data from old join */
2217
curr_join->join_free();
2218
if (make_simple_join(curr_join, curr_tmp_table))
2220
calc_group_buffer(curr_join, group_list);
2221
count_field_types(select_lex, &curr_join->tmp_table_param,
2222
curr_join->tmp_all_fields1,
2223
curr_join->select_distinct && !curr_join->group_list);
2224
curr_join->tmp_table_param.hidden_field_count=
2225
(curr_join->tmp_all_fields1.elements-
2226
curr_join->tmp_fields_list1.elements);
2229
if (exec_tmp_table2)
2230
curr_tmp_table= exec_tmp_table2;
2233
/* group data to new table */
2236
If the access method is loose index scan then all MIN/MAX
2237
functions are precomputed, and should be treated as regular
2238
functions. See extended comment in JOIN::exec.
2240
if (curr_join->join_tab->is_using_loose_index_scan())
2241
curr_join->tmp_table_param.precomputed_group_by= true;
2243
if (!(curr_tmp_table=
2244
exec_tmp_table2= create_tmp_table(thd,
2245
&curr_join->tmp_table_param,
2248
curr_join->select_distinct &&
2249
!curr_join->group_list,
2250
1, curr_join->select_options,
2254
curr_join->exec_tmp_table2= exec_tmp_table2;
2256
if (curr_join->group_list)
2258
thd_proc_info(thd, "Creating sort index");
2259
if (curr_join->join_tab == join_tab && save_join_tab())
2263
if (create_sort_index(thd, curr_join, curr_join->group_list,
2264
HA_POS_ERROR, HA_POS_ERROR, false) ||
2265
make_group_fields(this, curr_join))
2269
sortorder= curr_join->sortorder;
2272
thd_proc_info(thd, "Copying to group table");
2274
if (curr_join != this)
2278
curr_join->sum_funcs= sum_funcs2;
2279
curr_join->sum_funcs_end= sum_funcs_end2;
2283
curr_join->alloc_func_list();
2284
sum_funcs2= curr_join->sum_funcs;
2285
sum_funcs_end2= curr_join->sum_funcs_end;
2288
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2291
curr_join->group_list= 0;
2292
if (!curr_join->sort_and_group &&
2293
curr_join->const_tables != curr_join->tables)
2294
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2295
if (setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) ||
2296
(tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2301
end_read_record(&curr_join->join_tab->read_record);
2302
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
2303
curr_join->join_tab[0].table= 0; // Table is freed
2305
// No sum funcs anymore
2308
items2= items1 + all_fields.elements;
2309
if (change_to_use_tmp_fields(thd, items2,
2310
tmp_fields_list2, tmp_all_fields2,
2311
fields_list.elements, tmp_all_fields1))
2313
curr_join->tmp_fields_list2= tmp_fields_list2;
2314
curr_join->tmp_all_fields2= tmp_all_fields2;
2316
curr_fields_list= &curr_join->tmp_fields_list2;
2317
curr_all_fields= &curr_join->tmp_all_fields2;
2318
curr_join->set_items_ref_array(items2);
2319
curr_join->tmp_table_param.field_count+=
2320
curr_join->tmp_table_param.sum_func_count;
2321
curr_join->tmp_table_param.sum_func_count= 0;
2323
if (curr_tmp_table->distinct)
2324
curr_join->select_distinct=0; /* Each row is unique */
2326
curr_join->join_free(); /* Free quick selects */
2327
if (curr_join->select_distinct && ! curr_join->group_list)
2329
thd_proc_info(thd, "Removing duplicates");
2330
if (curr_join->tmp_having)
2331
curr_join->tmp_having->update_used_tables();
2332
if (remove_duplicates(curr_join, curr_tmp_table,
2333
*curr_fields_list, curr_join->tmp_having))
2335
curr_join->tmp_having=0;
2336
curr_join->select_distinct=0;
2338
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
2339
if (make_simple_join(curr_join, curr_tmp_table))
2341
calc_group_buffer(curr_join, curr_join->group_list);
2342
count_field_types(select_lex, &curr_join->tmp_table_param,
2343
*curr_all_fields, 0);
2347
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
2349
if (make_group_fields(this, curr_join))
2356
init_items_ref_array();
2357
items3= ref_pointer_array + (all_fields.elements*4);
2358
setup_copy_fields(thd, &curr_join->tmp_table_param,
2359
items3, tmp_fields_list3, tmp_all_fields3,
2360
curr_fields_list->elements, *curr_all_fields);
2361
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
2362
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
2363
tmp_table_param.save_copy_field_end=
2364
curr_join->tmp_table_param.copy_field_end;
2365
curr_join->tmp_all_fields3= tmp_all_fields3;
2366
curr_join->tmp_fields_list3= tmp_fields_list3;
2370
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
2371
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
2372
curr_join->tmp_table_param.copy_field_end=
2373
tmp_table_param.save_copy_field_end;
2375
curr_fields_list= &tmp_fields_list3;
2376
curr_all_fields= &tmp_all_fields3;
2377
curr_join->set_items_ref_array(items3);
2379
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2381
setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) ||
2382
thd->is_fatal_error)
2385
if (curr_join->group_list || curr_join->order)
2387
thd_proc_info(thd, "Sorting result");
2388
/* If we have already done the group, add HAVING to sorted table */
2389
if (curr_join->tmp_having && ! curr_join->group_list &&
2390
! curr_join->sort_and_group)
2392
// Some tables may have been const
2393
curr_join->tmp_having->update_used_tables();
2394
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
2395
table_map used_tables= (curr_join->const_table_map |
2396
curr_table->table->map);
2398
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having,
2401
if (sort_table_cond)
2403
if (!curr_table->select)
2404
if (!(curr_table->select= new SQL_SELECT))
2406
if (!curr_table->select->cond)
2407
curr_table->select->cond= sort_table_cond;
2408
else // This should never happen
2410
if (!(curr_table->select->cond=
2411
new Item_cond_and(curr_table->select->cond,
2415
Item_cond_and do not need fix_fields for execution, its parameters
2416
are fixed or do not need fix_fields, too
2418
curr_table->select->cond->quick_fix_field();
2420
curr_table->select_cond= curr_table->select->cond;
2421
curr_table->select_cond->top_level_item();
2422
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
2429
curr_join->select_limit= HA_POS_ERROR;
2433
We can abort sorting after thd->select_limit rows if we there is no
2434
WHERE clause for any tables after the sorted one.
2436
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
2437
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
2438
for (; curr_table < end_table ; curr_table++)
2441
table->keyuse is set in the case there was an original WHERE clause
2442
on the table that was optimized away.
2444
if (curr_table->select_cond ||
2445
(curr_table->keyuse && !curr_table->first_inner))
2447
/* We have to sort all rows */
2448
curr_join->select_limit= HA_POS_ERROR;
2453
if (curr_join->join_tab == join_tab && save_join_tab())
2458
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
2459
chose FILESORT to be faster than INDEX SCAN or there is no
2460
suitable index present.
2461
Note, that create_sort_index calls test_if_skip_sort_order and may
2462
finally replace sorting with index scan if there is a LIMIT clause in
2463
the query. XXX: it's never shown in EXPLAIN!
2464
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
2466
if (create_sort_index(thd, curr_join,
2467
curr_join->group_list ?
2468
curr_join->group_list : curr_join->order,
2469
curr_join->select_limit,
2470
(select_options & OPTION_FOUND_ROWS ?
2471
HA_POS_ERROR : unit->select_limit_cnt),
2472
curr_join->group_list ? true : false))
2474
sortorder= curr_join->sortorder;
2475
if (curr_join->const_tables != curr_join->tables &&
2476
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
2479
If no IO cache exists for the first table then we are using an
2480
INDEX SCAN and no filesort. Thus we should not remove the sorted
2481
attribute on the INDEX SCAN.
2487
/* XXX: When can we have here thd->is_error() not zero? */
2488
if (thd->is_error())
2490
error= thd->is_error();
2493
curr_join->having= curr_join->tmp_having;
2494
curr_join->fields= curr_fields_list;
2497
thd_proc_info(thd, "Sending data");
2498
result->send_fields(*curr_fields_list,
2499
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2500
error= do_select(curr_join, curr_fields_list, NULL);
2501
thd->limit_found_rows= curr_join->send_records;
2504
/* Accumulate the counts from all join iterations of all join parts. */
2505
thd->examined_row_count+= curr_join->examined_rows;
2508
With EXPLAIN EXTENDED we have to restore original ref_array
2509
for a derived table which is always materialized.
2510
Otherwise we would not be able to print the query correctly.
2513
(thd->lex->describe & DESCRIBE_EXTENDED) &&
2514
select_lex->linkage == DERIVED_TABLE_TYPE)
2515
set_items_ref_array(items0);
2525
Return error that hold JOIN.
2531
select_lex->join= 0;
2535
if (join_tab != tmp_join->join_tab)
2537
JOIN_TAB *tab, *end;
2538
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
2541
tmp_join->tmp_join= 0;
2542
tmp_table_param.copy_field=0;
2543
return(tmp_join->destroy());
2548
if (exec_tmp_table1)
2549
exec_tmp_table1->free_tmp_table(thd);
2550
if (exec_tmp_table2)
2551
exec_tmp_table2->free_tmp_table(thd);
2553
delete_dynamic(&keyuse);
2560
316
An entry point to single-unit select (a select without UNION).
2562
@param thd thread handler
318
@param session thread handler
2563
319
@param rref_pointer_array a reference to ref_pointer_array of
2564
320
the top-level select_lex for this query
2565
321
@param tables list of all tables used in this query.
2566
322
The tables have been pre-opened.
2567
@param wild_num number of wildcards used in the top level
323
@param wild_num number of wildcards used in the top level
2568
324
select of this query.
2569
325
For example statement
2570
326
SELECT *, t1.*, catalog.t2.* FROM t0, t1, t2;
2743
Convert a subquery predicate into a TableList semi-join nest
2746
convert_subq_to_sj()
2747
parent_join Parent join, the one that has subq_pred in its WHERE/ON
2749
subq_pred Subquery predicate to be converted
2752
Convert a subquery predicate into a TableList semi-join nest. All the
2753
prerequisites are already checked, so the conversion is always successfull.
2755
Prepared Statements: the transformation is permanent:
2756
- Changes in TableList structures are naturally permanent
2757
- Item tree changes are performed on statement MEM_ROOT:
2758
= we activate statement MEM_ROOT
2759
= this function is called before the first fix_prepare_information
2762
This is intended because the criteria for subquery-to-sj conversion remain
2763
constant for the lifetime of the Prepared Statement.
2767
true Out of memory error
2770
bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
2772
SELECT_LEX *parent_lex= parent_join->select_lex;
2773
TableList *emb_tbl_nest= NULL;
2774
List<TableList> *emb_join_list= &parent_lex->top_join_list;
2775
THD *thd= parent_join->thd;
2778
1. Find out where to put the predicate into.
2779
Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
2781
if ((void*)subq_pred->expr_join_nest != (void*)1)
2783
if (subq_pred->expr_join_nest->nested_join)
2788
... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
2790
The sj-nest will be inserted into the brackets nest.
2792
emb_tbl_nest= subq_pred->expr_join_nest;
2793
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2795
else if (!subq_pred->expr_join_nest->outer_join)
2800
... INNER JOIN tblX ON (subquery AND whatever) ...
2802
The sj-nest will be tblX's "sibling", i.e. another child of its
2803
parent. This is ok because tblX is joined as an inner join.
2805
emb_tbl_nest= subq_pred->expr_join_nest->embedding;
2807
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2809
else if (!subq_pred->expr_join_nest->nested_join)
2811
TableList *outer_tbl= subq_pred->expr_join_nest;
2812
TableList *wrap_nest;
2816
... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
2818
we'll need to convert it into:
2820
... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
2822
|<----- wrap_nest ---->|
2824
Q: other subqueries may be pointing to this element. What to do?
2825
A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
2826
But we'll need to fix other pointers.
2827
A2: Another way: have TableList::next_ptr so the following
2828
subqueries know the table has been nested.
2829
A3: changes in the TableList::outer_join will make everything work
2832
if (!(wrap_nest= alloc_join_nest(parent_join->thd)))
2836
wrap_nest->embedding= outer_tbl->embedding;
2837
wrap_nest->join_list= outer_tbl->join_list;
2838
wrap_nest->alias= (char*) "(sj-wrap)";
2840
wrap_nest->nested_join->join_list.empty();
2841
wrap_nest->nested_join->join_list.push_back(outer_tbl);
2843
outer_tbl->embedding= wrap_nest;
2844
outer_tbl->join_list= &wrap_nest->nested_join->join_list;
2847
wrap_nest will take place of outer_tbl, so move the outer join flag
2850
wrap_nest->outer_join= outer_tbl->outer_join;
2851
outer_tbl->outer_join= 0;
2853
wrap_nest->on_expr= outer_tbl->on_expr;
2854
outer_tbl->on_expr= NULL;
2856
List_iterator<TableList> li(*wrap_nest->join_list);
2860
if (tbl == outer_tbl)
2862
li.replace(wrap_nest);
2867
Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
2868
semi-join nest into it
2870
emb_join_list= &wrap_nest->nested_join->join_list;
2871
emb_tbl_nest= wrap_nest;
2876
nested_join_st *nested_join;
2877
if (!(sj_nest= alloc_join_nest(parent_join->thd)))
2881
nested_join= sj_nest->nested_join;
2883
sj_nest->join_list= emb_join_list;
2884
sj_nest->embedding= emb_tbl_nest;
2885
sj_nest->alias= (char*) "(sj-nest)";
2886
/* Nests do not participate in those 'chains', so: */
2887
/* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
2888
emb_join_list->push_back(sj_nest);
2891
nested_join->used_tables and nested_join->not_null_tables are
2892
initialized in simplify_joins().
2896
2. Walk through subquery's top list and set 'embedding' to point to the
2899
st_select_lex *subq_lex= subq_pred->unit->first_select();
2900
nested_join->join_list.empty();
2901
List_iterator_fast<TableList> li(subq_lex->top_join_list);
2902
TableList *tl, *last_leaf;
2905
tl->embedding= sj_nest;
2906
tl->join_list= &nested_join->join_list;
2907
nested_join->join_list.push_back(tl);
2911
Reconnect the next_leaf chain.
2912
TODO: Do we have to put subquery's tables at the end of the chain?
2913
Inserting them at the beginning would be a bit faster.
2914
NOTE: We actually insert them at the front! That's because the order is
2915
reversed in this list.
2917
for (tl= parent_lex->leaf_tables; tl->next_leaf; tl= tl->next_leaf) {};
2918
tl->next_leaf= subq_lex->leaf_tables;
2922
Same as above for next_local chain
2923
(a theory: a next_local chain always starts with ::leaf_tables
2924
because view's tables are inserted after the view)
2926
for (tl= parent_lex->leaf_tables; tl->next_local; tl= tl->next_local) {};
2927
tl->next_local= subq_lex->leaf_tables;
2929
/* A theory: no need to re-connect the next_global chain */
2931
/* 3. Remove the original subquery predicate from the WHERE/ON */
2933
// The subqueries were replaced for Item_int(1) earlier
2934
subq_pred->exec_method= Item_in_subselect::SEMI_JOIN; // for subsequent executions
2935
/*TODO: also reset the 'with_subselect' there. */
2937
/* n. Adjust the parent_join->tables counter */
2938
uint32_t table_no= parent_join->tables;
2939
/* n. Walk through child's tables and adjust table->map */
2940
for (tl= subq_lex->leaf_tables; tl; tl= tl->next_leaf, table_no++)
2942
tl->table->tablenr= table_no;
2943
tl->table->map= ((table_map)1) << table_no;
2944
SELECT_LEX *old_sl= tl->select_lex;
2945
tl->select_lex= parent_join->select_lex;
2946
for(TableList *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)
2947
emb->select_lex= parent_join->select_lex;
2949
parent_join->tables += subq_lex->join->tables;
2952
Put the subquery's WHERE into semi-join's sj_on_expr
2953
Add the subquery-induced equalities too.
2955
SELECT_LEX *save_lex= thd->lex->current_select;
2956
thd->lex->current_select=subq_lex;
2957
if (!subq_pred->left_expr->fixed &&
2958
subq_pred->left_expr->fix_fields(thd, &subq_pred->left_expr))
2960
thd->lex->current_select=save_lex;
2962
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
2963
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables() |
2964
subq_pred->left_expr->used_tables();
2965
sj_nest->sj_on_expr= subq_lex->where;
2968
Create the IN-equalities and inject them into semi-join's ON expression.
2969
Additionally, for InsideOut strategy
2970
- Record the number of IN-equalities.
2971
- Create list of pointers to (oe1, ..., ieN). We'll need the list to
2972
see which of the expressions are bound and which are not (for those
2973
we'll produce a distinct stream of (ie_i1,...ie_ik).
2975
(TODO: can we just create a list of pointers and hope the expressions
2976
will not substitute themselves on fix_fields()? or we need to wrap
2977
them into Item_direct_view_refs and store pointers to those. The
2978
pointers to Item_direct_view_refs are guaranteed to be stable as
2979
Item_direct_view_refs doesn't substitute itself with anything in
2980
Item_direct_view_ref::fix_fields.
2982
sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
2983
sj_nest->nested_join->sj_outer_expr_list.empty();
2985
if (subq_pred->left_expr->cols() == 1)
2987
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr);
2989
Item *item_eq= new Item_func_eq(subq_pred->left_expr,
2990
subq_lex->ref_pointer_array[0]);
2991
item_eq->name= (char*)subq_sj_cond_name;
2992
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
2996
for (uint32_t i= 0; i < subq_pred->left_expr->cols(); i++)
2998
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->
3001
new Item_func_eq(subq_pred->left_expr->element_index(i),
3002
subq_lex->ref_pointer_array[i]);
3003
item_eq->name= (char*)subq_sj_cond_name + (i % 64);
3004
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3007
/* Fix the created equality and AND */
3008
sj_nest->sj_on_expr->fix_fields(parent_join->thd, &sj_nest->sj_on_expr);
3011
Walk through sj nest's WHERE and ON expressions and call
3012
item->fix_table_changes() for all items.
3014
sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr);
3015
fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
3018
/* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
3019
subq_lex->master_unit()->exclude_level();
3021
/* Inject sj_on_expr into the parent's WHERE or ON */
3024
emb_tbl_nest->on_expr= and_items(emb_tbl_nest->on_expr,
3025
sj_nest->sj_on_expr);
3026
emb_tbl_nest->on_expr->fix_fields(parent_join->thd, &emb_tbl_nest->on_expr);
3030
/* Inject into the WHERE */
3031
parent_join->conds= and_items(parent_join->conds, sj_nest->sj_on_expr);
3032
parent_join->conds->fix_fields(parent_join->thd, &parent_join->conds);
3033
parent_join->select_lex->where= parent_join->conds;
3041
Convert candidate subquery predicates to semi-joins
3044
JOIN::flatten_subqueries()
3047
Convert candidate subquery predicates to semi-joins.
3054
bool JOIN::flatten_subqueries()
3056
Item_in_subselect **in_subq;
3057
Item_in_subselect **in_subq_end;
3059
if (sj_subselects.elements() == 0)
3062
/* 1. Fix children subqueries */
3063
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
3064
in_subq != in_subq_end; in_subq++)
3066
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3067
child_join->outer_tables = child_join->tables;
3068
if (child_join->flatten_subqueries())
3070
(*in_subq)->sj_convert_priority=
3071
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
3074
//dump_TableList_struct(select_lex, select_lex->leaf_tables);
3076
2. Pick which subqueries to convert:
3077
sort the subquery array
3078
- prefer correlated subqueries over uncorrelated;
3079
- prefer subqueries that have greater number of outer tables;
3081
sj_subselects.sort(subq_sj_candidate_cmp);
3082
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
3083
/* Replace all subqueries to be flattened with Item_int(1) */
3084
for (in_subq= sj_subselects.front();
3085
in_subq != in_subq_end &&
3086
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3089
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
3093
for (in_subq= sj_subselects.front();
3094
in_subq != in_subq_end &&
3095
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3098
if (convert_subq_to_sj(this, *in_subq))
3102
/* 3. Finalize those we didn't convert */
3103
for (; in_subq!= in_subq_end; in_subq++)
3105
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3106
Item_subselect::trans_res res;
3107
(*in_subq)->changed= 0;
3108
(*in_subq)->fixed= 0;
3109
res= (*in_subq)->select_transformer(child_join);
3110
if (res == Item_subselect::RES_ERROR)
3113
(*in_subq)->changed= 1;
3114
(*in_subq)->fixed= 1;
3116
Item *substitute= (*in_subq)->substitution;
3117
bool do_fix_fields= !(*in_subq)->substitution->fixed;
3118
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
3121
//if ((*in_subq)->fix_fields(thd, (*in_subq)->ref_ptr))
3124
sj_subselects.clear();
3130
Setup for execution all subqueries of a query, for which the optimizer
3131
chose hash semi-join.
3133
@details Iterate over all subqueries of the query, and if they are under an
3134
IN predicate, and the optimizer chose to compute it via hash semi-join:
3135
- try to initialize all data structures needed for the materialized execution
3136
of the IN predicate,
3137
- if this fails, then perform the IN=>EXISTS transformation which was
3138
previously blocked during JOIN::prepare.
3140
This method is part of the "code generation" query processing phase.
3142
This phase must be called after substitute_for_best_equal_field() because
3143
that function may replace items with other items from a multiple equality,
3144
and we need to reference the correct items in the index access method of the
3147
@return Operation status
3148
@retval false success.
3149
@retval true error occurred.
3152
bool JOIN::setup_subquery_materialization()
3154
for (SELECT_LEX_UNIT *un= select_lex->first_inner_unit(); un;
3155
un= un->next_unit())
3157
for (SELECT_LEX *sl= un->first_select(); sl; sl= sl->next_select())
3159
Item_subselect *subquery_predicate= sl->master_unit()->item;
3160
if (subquery_predicate &&
3161
subquery_predicate->substype() == Item_subselect::IN_SUBS)
3163
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
3164
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
3165
in_subs->setup_engine())
3175
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3178
find_eq_ref_candidate()
3179
table Table to be checked
3180
sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
3184
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3187
Check again if it is feasible to factor common parts with constant table
3191
true - There exists an eq_ref(outer-tables) candidate
3195
bool find_eq_ref_candidate(Table *table, table_map sj_inner_tables)
3197
KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
3202
while (1) /* For each key */
3205
KEY *keyinfo= table->key_info + key;
3206
key_part_map bound_parts= 0;
3207
if ((keyinfo->flags & HA_NOSAME) == HA_NOSAME)
3209
do /* For all equalities on all key parts */
3211
/* Check if this is "t.keypart = expr(outer_tables) */
3212
if (!(keyuse->used_tables & sj_inner_tables) &&
3213
!(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
3215
bound_parts |= 1 << keyuse->keypart;
3218
} while (keyuse->key == key && keyuse->table == table);
3220
if (bound_parts == PREV_BITS(uint, keyinfo->key_parts))
3222
if (keyuse->table != table)
3230
if (keyuse->table != table)
3233
while (keyuse->key == key);
3242
Pull tables out of semi-join nests, if possible
3245
pull_out_semijoin_tables()
3246
join The join where to do the semi-join flattening
3249
Try to pull tables out of semi-join nests.
3252
When this function is called, the join may have several semi-join nests
3253
(possibly within different semi-join nests), but it is guaranteed that
3254
one semi-join nest does not contain another.
3257
A table can be pulled out of the semi-join nest if
3258
- It is a constant table
3262
* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer
3264
* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.
3265
* Semi-join nests TableList::sj_inner_tables
3267
This operation is (and should be) performed at each PS execution since
3268
tables may become/cease to be constant across PS reexecutions.
3272
1 - Out of memory error
3275
int pull_out_semijoin_tables(JOIN *join)
3278
List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);
3280
/* Try pulling out of the each of the semi-joins */
3281
while ((sj_nest= sj_list_it++))
3283
/* Action #1: Mark the constant tables to be pulled out */
3284
table_map pulled_tables= 0;
3286
List_iterator<TableList> child_li(sj_nest->nested_join->join_list);
3288
while ((tbl= child_li++))
3292
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
3293
if (tbl->table->map & join->const_table_map)
3295
pulled_tables |= tbl->table->map;
3301
Action #2: Find which tables we can pull out based on
3302
update_ref_and_keys() data. Note that pulling one table out can allow
3303
us to pull out some other tables too.
3305
bool pulled_a_table;
3308
pulled_a_table= false;
3310
while ((tbl= child_li++))
3312
if (tbl->table && !(pulled_tables & tbl->table->map))
3314
if (find_eq_ref_candidate(tbl->table,
3315
sj_nest->nested_join->used_tables &
3318
pulled_a_table= true;
3319
pulled_tables |= tbl->table->map;
3323
} while (pulled_a_table);
3326
if ((sj_nest)->nested_join->used_tables == pulled_tables)
3328
(sj_nest)->sj_inner_tables= 0;
3329
while ((tbl= child_li++))
3332
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3337
/* Record the bitmap of inner tables, mark the inner tables */
3338
table_map inner_tables=(sj_nest)->nested_join->used_tables &
3340
(sj_nest)->sj_inner_tables= inner_tables;
3341
while ((tbl= child_li++))
3345
if (inner_tables & tbl->table->map)
3346
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
3348
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3356
471
/*****************************************************************************
3357
Create JOIN_TABS, make a guess about the table types,
472
Create JoinTableS, make a guess about the table types,
3358
473
Approximate how many records will be used in each table
3359
474
*****************************************************************************/
3362
static ha_rows get_quick_record_count(THD *thd, SQL_SELECT *select,
3364
const key_map *keys,ha_rows limit)
475
ha_rows get_quick_record_count(Session *session, SQL_SELECT *select, Table *table, const key_map *keys,ha_rows limit)
3367
if (check_stack_overrun(thd, STACK_MIN_SIZE, NULL))
478
if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))
3368
479
return(0); // Fatal error flag is set
3371
482
select->head=table;
3372
483
table->reginfo.impossible_range=0;
3373
if ((error= select->test_quick_select(thd, *(key_map *)keys,(table_map) 0,
484
if ((error= select->test_quick_select(session, *(key_map *)keys,(table_map) 0,
3374
485
limit, 0, false)) == 1)
3375
486
return(select->quick->records);
3376
487
if (error == -1)
3382
493
return(HA_POS_ERROR); /* This shouldn't happend */
3386
This structure is used to collect info on potentially sargable
3387
predicates in order to check whether they become sargable after
3388
reading const tables.
3389
We form a bitmap of indexes that can be used for sargable predicates.
3390
Only such indexes are involved in range analysis.
3392
typedef struct st_sargable_param
3394
Field *field; /* field against which to check sargability */
3395
Item **arg_value; /* values of potential keys for lookups */
3396
uint32_t num_values; /* number of values in the above array */
3400
Calculate the best possible join and initialize the join structure.
3409
make_join_statistics(JOIN *join, TableList *tables, COND *conds,
3410
DYNAMIC_ARRAY *keyuse_array)
3414
uint32_t i,table_count,const_count,key;
3415
table_map found_const_table_map, all_table_map, found_ref, refs;
3416
key_map const_ref, eq_part;
3417
Table **table_vector;
3418
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
3419
KEYUSE *keyuse,*start_keyuse;
3420
table_map outer_join=0;
3421
SARGABLE_PARAM *sargables= 0;
3422
JOIN_TAB *stat_vector[MAX_TABLES+1];
3424
table_count=join->tables;
3425
stat=(JOIN_TAB*) join->thd->calloc(sizeof(JOIN_TAB)*table_count);
3426
stat_ref=(JOIN_TAB**) join->thd->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
3427
table_vector=(Table**) join->thd->alloc(sizeof(Table*)*(table_count*2));
3428
if (!stat || !stat_ref || !table_vector)
3429
return(1); // Eom /* purecov: inspected */
3431
join->best_ref=stat_vector;
3433
stat_end=stat+table_count;
3434
found_const_table_map= all_table_map=0;
3439
s++, tables= tables->next_leaf, i++)
3441
TableList *embedding= tables->embedding;
3444
s->const_keys.init();
3445
s->checked_keys.init();
3446
s->needed_reg.init();
3447
table_vector[i]=s->table=table=tables->table;
3448
table->pos_in_table_list= tables;
3449
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
3452
table->file->print_error(error, MYF(0));
3455
table->quick_keys.clear_all();
3456
table->reginfo.join_tab=s;
3457
table->reginfo.not_exists_optimize=0;
3458
memset(table->const_key_parts, 0,
3459
sizeof(key_part_map)*table->s->keys);
3460
all_table_map|= table->map;
3462
s->info=0; // For describe
3464
s->dependent= tables->dep_tables;
3465
s->key_dependent= 0;
3466
if (tables->schema_table)
3467
table->file->stats.records= 2;
3468
table->quick_condition_rows= table->file->stats.records;
3470
s->on_expr_ref= &tables->on_expr;
3471
if (*s->on_expr_ref)
3473
/* s is the only inner table of an outer join */
3474
if (!table->file->stats.records && !embedding)
3476
s->dependent= 0; // Ignore LEFT JOIN depend.
3477
set_position(join,const_count++,s,(KEYUSE*) 0);
3480
outer_join|= table->map;
3481
s->embedding_map= 0;
3482
for (;embedding; embedding= embedding->embedding)
3483
s->embedding_map|= embedding->nested_join->nj_map;
3486
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
3488
/* s belongs to a nested join, maybe to several embedded joins */
3489
s->embedding_map= 0;
3492
nested_join_st *nested_join= embedding->nested_join;
3493
s->embedding_map|=nested_join->nj_map;
3494
s->dependent|= embedding->dep_tables;
3495
embedding= embedding->embedding;
3496
outer_join|= nested_join->used_tables;
3501
if ((table->file->stats.records <= 1) &&
3503
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && !join->no_const_tables)
3505
set_position(join,const_count++,s,(KEYUSE*) 0);
3509
join->outer_join=outer_join;
3511
if (join->outer_join)
3514
Build transitive closure for relation 'to be dependent on'.
3515
This will speed up the plan search for many cases with outer joins,
3516
as well as allow us to catch illegal cross references/
3517
Warshall's algorithm is used to build the transitive closure.
3518
As we use bitmaps to represent the relation the complexity
3519
of the algorithm is O((number of tables)^2).
3521
for (i= 0, s= stat ; i < table_count ; i++, s++)
3523
for (uint32_t j= 0 ; j < table_count ; j++)
3525
table= stat[j].table;
3526
if (s->dependent & table->map)
3527
s->dependent |= table->reginfo.join_tab->dependent;
3530
s->table->maybe_null= 1;
3532
/* Catch illegal cross references for outer joins */
3533
for (i= 0, s= stat ; i < table_count ; i++, s++)
3535
if (s->dependent & s->table->map)
3537
join->tables=0; // Don't use join->table
3538
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
3541
s->key_dependent= s->dependent;
3545
if (conds || outer_join)
3546
if (update_ref_and_keys(join->thd, keyuse_array, stat, join->tables,
3547
conds, join->cond_equal,
3548
~outer_join, join->select_lex, &sargables))
3551
/* Read tables with 0 or 1 rows (system tables) */
3552
join->const_table_map= 0;
3554
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
3561
join->const_table_map|=s->table->map;
3562
if ((tmp=join_read_const_table(s, p_pos)))
3565
return(1); // Fatal error
3568
found_const_table_map|= s->table->map;
3571
/* loop until no more const tables are found */
3575
more_const_tables_found:
3580
We only have to loop from stat_vector + const_count as
3581
set_position() will move all const_tables first in stat_vector
3584
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
3589
If equi-join condition by a key is null rejecting and after a
3590
substitution of a const table the key value happens to be null
3591
then we can state that there are no matches for this equi-join.
3593
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
3596
When performing an outer join operation if there are no matching rows
3597
for the single row of the outer table all the inner tables are to be
3598
null complemented and thus considered as constant tables.
3599
Here we apply this consideration to the case of outer join operations
3600
with a single inner table only because the case with nested tables
3601
would require a more thorough analysis.
3602
TODO. Apply single row substitution to null complemented inner tables
3603
for nested outer join operations.
3605
while (keyuse->table == table)
3607
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
3608
keyuse->val->is_null() && keyuse->null_rejecting)
3611
mark_as_null_row(table);
3612
found_const_table_map|= table->map;
3613
join->const_table_map|= table->map;
3614
set_position(join,const_count++,s,(KEYUSE*) 0);
3615
goto more_const_tables_found;
3621
if (s->dependent) // If dependent on some table
3623
// All dep. must be constants
3624
if (s->dependent & ~(found_const_table_map))
3626
if (table->file->stats.records <= 1L &&
3627
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
3628
!table->pos_in_table_list->embedding)
3632
join->const_table_map|=table->map;
3633
set_position(join,const_count++,s,(KEYUSE*) 0);
3634
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
3637
return(1); // Fatal error
3640
found_const_table_map|= table->map;
3644
/* check if table can be read by key or table only uses const refs */
3645
if ((keyuse=s->keyuse))
3648
while (keyuse->table == table)
3650
start_keyuse=keyuse;
3652
s->keys.set_bit(key); // QQ: remove this ?
3655
const_ref.clear_all();
3656
eq_part.clear_all();
3659
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
3661
if (!((~found_const_table_map) & keyuse->used_tables))
3662
const_ref.set_bit(keyuse->keypart);
3664
refs|=keyuse->used_tables;
3665
eq_part.set_bit(keyuse->keypart);
3668
} while (keyuse->table == table && keyuse->key == key);
3670
if (eq_part.is_prefix(table->key_info[key].key_parts) &&
3671
!table->pos_in_table_list->embedding)
3673
if ((table->key_info[key].flags & (HA_NOSAME))
3676
if (const_ref == eq_part)
3677
{ // Found everything for ref.
3681
join->const_table_map|=table->map;
3682
set_position(join,const_count++,s,start_keyuse);
3683
if (create_ref_for_key(join, s, start_keyuse,
3684
found_const_table_map))
3686
if ((tmp=join_read_const_table(s,
3687
join->positions+const_count-1)))
3690
return(1); // Fatal error
3693
found_const_table_map|= table->map;
3697
found_ref|= refs; // Table is const if all refs are const
3699
else if (const_ref == eq_part)
3700
s->const_keys.set_bit(key);
3705
} while (join->const_table_map & found_ref && ref_changed);
3708
Update info on indexes that can be used for search lookups as
3709
reading const tables may has added new sargable predicates.
3711
if (const_count && sargables)
3713
for( ; sargables->field ; sargables++)
3715
Field *field= sargables->field;
3716
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
3717
key_map possible_keys= field->key_start;
3718
possible_keys.intersect(field->table->keys_in_use_for_query);
3720
for (uint32_t j=0; j < sargables->num_values; j++)
3721
is_const&= sargables->arg_value[j]->const_item();
3723
join_tab[0].const_keys.merge(possible_keys);
3727
if (pull_out_semijoin_tables(join))
3730
/* Calc how many (possible) matched records in each table */
3732
for (s=stat ; s < stat_end ; s++)
3734
if (s->type == JT_SYSTEM || s->type == JT_CONST)
3736
/* Only one matching row */
3737
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
3740
/* Approximate found rows and time to read them */
3741
s->found_records=s->records=s->table->file->stats.records;
3742
s->read_time=(ha_rows) s->table->file->scan_time();
3745
Set a max range of how many seeks we can expect when using keys
3746
This is can't be to high as otherwise we are likely to use
3749
s->worst_seeks= cmin((double) s->found_records / 10,
3750
(double) s->read_time*3);
3751
if (s->worst_seeks < 2.0) // Fix for small tables
3755
Add to stat->const_keys those indexes for which all group fields or
3756
all select distinct fields participate in one index.
3758
add_group_and_distinct_keys(join, s);
3760
if (!s->const_keys.is_clear_all() &&
3761
!s->table->pos_in_table_list->embedding)
3765
select= make_select(s->table, found_const_table_map,
3766
found_const_table_map,
3767
*s->on_expr_ref ? *s->on_expr_ref : conds,
3771
records= get_quick_record_count(join->thd, select, s->table,
3772
&s->const_keys, join->row_limit);
3773
s->quick=select->quick;
3774
s->needed_reg=select->needed_reg;
3776
if (records == 0 && s->table->reginfo.impossible_range)
3779
Impossible WHERE or ON expression
3780
In case of ON, we mark that the we match one empty NULL row.
3781
In case of WHERE, don't set found_const_table_map to get the
3782
caller to abort with a zero row result.
3784
join->const_table_map|= s->table->map;
3785
set_position(join,const_count++,s,(KEYUSE*) 0);
3787
if (*s->on_expr_ref)
3789
/* Generate empty row */
3790
s->info= "Impossible ON condition";
3791
found_const_table_map|= s->table->map;
3793
mark_as_null_row(s->table); // All fields are NULL
3796
if (records != HA_POS_ERROR)
3798
s->found_records=records;
3799
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
3805
join->join_tab=stat;
3806
join->map2table=stat_ref;
3807
join->table= join->all_tables=table_vector;
3808
join->const_tables=const_count;
3809
join->found_const_table_map=found_const_table_map;
3811
/* Find an optimal join order of the non-constant tables. */
3812
if (join->const_tables != join->tables)
3814
optimize_keyuse(join, keyuse_array);
3815
if (choose_plan(join, all_table_map & ~join->const_table_map))
3820
memcpy(join->best_positions, join->positions,
3821
sizeof(POSITION)*join->const_tables);
3822
join->best_read=1.0;
3824
/* Generate an execution plan from the found optimal join order. */
3825
return(join->thd->killed || get_best_combination(join));
3829
496
/*****************************************************************************
3830
497
Check with keys are used and with tables references with tables
3831
498
Updates in stat:
3834
501
keyuse Pointer to possible keys
3835
502
*****************************************************************************/
3837
/// Used when finding key fields
3838
typedef struct key_field_t {
3840
Item *val; ///< May be empty if diff constant
3842
uint optimize; // KEY_OPTIMIZE_*
3845
If true, the condition this struct represents will not be satisfied
3848
bool null_rejecting;
3849
bool *cond_guard; /* See KEYUSE::cond_guard */
3850
uint32_t sj_pred_no; /* See KEYUSE::sj_pred_no */
3854
Merge new key definitions to old ones, remove those not used in both.
3856
This is called for OR between different levels.
3858
To be able to do 'ref_or_null' we merge a comparison of a column
3859
and 'column IS NULL' to one test. This is useful for sub select queries
3860
that are internally transformed to something like:.
3863
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
3866
KEY_FIELD::null_rejecting is processed as follows: @n
3867
result has null_rejecting=true if it is set for both ORed references.
3869
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
3870
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
3873
The result of this is that we're missing some 'ref' accesses.
3874
OptimizerTeam: Fix this
3878
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
3881
if (start == new_fields)
3882
return start; // Impossible or
3883
if (new_fields == end)
3884
return start; // No new fields, skip all
3886
KEY_FIELD *first_free=new_fields;
3888
/* Mark all found fields in old array */
3889
for (; new_fields != end ; new_fields++)
3891
for (KEY_FIELD *old=start ; old != first_free ; old++)
3893
if (old->field == new_fields->field)
3896
NOTE: below const_item() call really works as "!used_tables()", i.e.
3897
it can return false where it is feasible to make it return true.
3899
The cause is as follows: Some of the tables are already known to be
3900
const tables (the detection code is in make_join_statistics(),
3901
above the update_ref_and_keys() call), but we didn't propagate
3902
information about this: Table::const_table is not set to true, and
3903
Item::update_used_tables() hasn't been called for each item.
3904
The result of this is that we're missing some 'ref' accesses.
3905
TODO: OptimizerTeam: Fix this
3907
if (!new_fields->val->const_item())
3910
If the value matches, we can use the key reference.
3911
If not, we keep it until we have examined all new values
3913
if (old->val->eq(new_fields->val, old->field->binary()))
3915
old->level= and_level;
3916
old->optimize= ((old->optimize & new_fields->optimize &
3917
KEY_OPTIMIZE_EXISTS) |
3918
((old->optimize | new_fields->optimize) &
3919
KEY_OPTIMIZE_REF_OR_NULL));
3920
old->null_rejecting= (old->null_rejecting &&
3921
new_fields->null_rejecting);
3924
else if (old->eq_func && new_fields->eq_func &&
3925
old->val->eq_by_collation(new_fields->val,
3926
old->field->binary(),
3927
old->field->charset()))
3930
old->level= and_level;
3931
old->optimize= ((old->optimize & new_fields->optimize &
3932
KEY_OPTIMIZE_EXISTS) |
3933
((old->optimize | new_fields->optimize) &
3934
KEY_OPTIMIZE_REF_OR_NULL));
3935
old->null_rejecting= (old->null_rejecting &&
3936
new_fields->null_rejecting);
3938
else if (old->eq_func && new_fields->eq_func &&
3939
((old->val->const_item() && old->val->is_null()) ||
3940
new_fields->val->is_null()))
3942
/* field = expression OR field IS NULL */
3943
old->level= and_level;
3944
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
3946
Remember the NOT NULL value unless the value does not depend
3949
if (!old->val->used_tables() && old->val->is_null())
3950
old->val= new_fields->val;
3951
/* The referred expression can be NULL: */
3952
old->null_rejecting= 0;
3957
We are comparing two different const. In this case we can't
3958
use a key-lookup on this so it's better to remove the value
3959
and let the range optimzier handle it
3961
if (old == --first_free) // If last item
3963
*old= *first_free; // Remove old value
3964
old--; // Retry this value
3969
/* Remove all not used items */
3970
for (KEY_FIELD *old=start ; old != first_free ;)
3972
if (old->level != and_level)
3973
{ // Not used in all levels
3974
if (old == --first_free)
3976
*old= *first_free; // Remove old value
3986
Add a possible key to array of possible keys if it's usable as a key
3988
@param key_fields Pointer to add key, if usable
3989
@param and_level And level, to be stored in KEY_FIELD
3990
@param cond Condition predicate
3991
@param field Field used in comparision
3992
@param eq_func True if we used =, <=> or IS NULL
3993
@param value Value used for comparison with field
3994
@param usable_tables Tables which can be used for key optimization
3995
@param sargables IN/OUT Array of found sargable candidates
3998
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
3999
table, we store this to be able to do not exists optimization later.
4002
*key_fields is incremented if we stored a key in the array
4006
add_key_field(KEY_FIELD **key_fields,uint32_t and_level, Item_func *cond,
4007
Field *field, bool eq_func, Item **value, uint32_t num_values,
4008
table_map usable_tables, SARGABLE_PARAM **sargables)
4010
uint32_t exists_optimize= 0;
4011
if (!(field->flags & PART_KEY_FLAG))
4013
// Don't remove column IS NULL on a LEFT JOIN table
4014
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4015
!field->table->maybe_null || field->null_ptr)
4016
return; // Not a key. Skip it
4017
exists_optimize= KEY_OPTIMIZE_EXISTS;
4018
assert(num_values == 1);
4022
table_map used_tables=0;
4024
for (uint32_t i=0; i<num_values; i++)
4026
used_tables|=(value[i])->used_tables();
4027
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
4032
if (!(usable_tables & field->table->map))
4034
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4035
!field->table->maybe_null || field->null_ptr)
4036
return; // Can't use left join optimize
4037
exists_optimize= KEY_OPTIMIZE_EXISTS;
4041
JOIN_TAB *stat=field->table->reginfo.join_tab;
4042
key_map possible_keys=field->key_start;
4043
possible_keys.intersect(field->table->keys_in_use_for_query);
4044
stat[0].keys.merge(possible_keys); // Add possible keys
4047
Save the following cases:
4049
Field LIKE constant where constant doesn't start with a wildcard
4050
Field = field2 where field2 is in a different table
4057
stat[0].key_dependent|=used_tables;
4060
for (uint32_t i=0; i<num_values; i++)
4062
if (!(is_const&= value[i]->const_item()))
4066
stat[0].const_keys.merge(possible_keys);
4070
Save info to be able check whether this predicate can be
4071
considered as sargable for range analisis after reading const tables.
4072
We do not save info about equalities as update_const_equal_items
4073
will take care of updating info on keys from sargable equalities.
4076
(*sargables)->field= field;
4077
(*sargables)->arg_value= value;
4078
(*sargables)->num_values= num_values;
4081
We can't always use indexes when comparing a string index to a
4082
number. cmp_type() is checked to allow compare of dates to numbers.
4083
eq_func is NEVER true when num_values > 1
4088
Additional optimization: if we're processing
4089
"t.key BETWEEN c1 AND c1" then proceed as if we were processing
4091
TODO: This is a very limited fix. A more generic fix is possible.
4092
There are 2 options:
4093
A) Make equality propagation code be able to handle BETWEEN
4094
(including cases like t1.key BETWEEN t2.key AND t3.key)
4095
B) Make range optimizer to infer additional "t.key = c" equalities
4096
and use them in equality propagation process (see details in
4099
if ((cond->functype() != Item_func::BETWEEN) ||
4100
((Item_func_between*) cond)->negated ||
4101
!value[0]->eq(value[1], field->binary()))
4106
if (field->result_type() == STRING_RESULT)
4108
if ((*value)->result_type() != STRING_RESULT)
4110
if (field->cmp_type() != (*value)->result_type())
4116
We can't use indexes if the effective collation
4117
of the operation differ from the field collation.
4119
if (field->cmp_type() == STRING_RESULT &&
4120
((Field_str*)field)->charset() != cond->compare_collation())
4127
For the moment eq_func is always true. This slot is reserved for future
4128
extensions where we want to remembers other things than just eq comparisons
4131
/* Store possible eq field */
4132
(*key_fields)->field= field;
4133
(*key_fields)->eq_func= eq_func;
4134
(*key_fields)->val= *value;
4135
(*key_fields)->level= and_level;
4136
(*key_fields)->optimize= exists_optimize;
4138
If the condition has form "tbl.keypart = othertbl.field" and
4139
othertbl.field can be NULL, there will be no matches if othertbl.field
4141
We use null_rejecting in add_not_null_conds() to add
4142
'othertbl.field IS NOT NULL' to tab->select_cond.
4144
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
4145
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
4146
((*value)->type() == Item::FIELD_ITEM) &&
4147
((Item_field*)*value)->field->maybe_null());
4148
(*key_fields)->cond_guard= NULL;
4149
(*key_fields)->sj_pred_no= (cond->name >= subq_sj_cond_name &&
4150
cond->name < subq_sj_cond_name + 64)?
4151
cond->name - subq_sj_cond_name: UINT_MAX;
4156
Add possible keys to array of possible keys originated from a simple
4159
@param key_fields Pointer to add key, if usable
4160
@param and_level And level, to be stored in KEY_FIELD
4161
@param cond Condition predicate
4162
@param field Field used in comparision
4163
@param eq_func True if we used =, <=> or IS NULL
4164
@param value Value used for comparison with field
4165
Is NULL for BETWEEN and IN
4166
@param usable_tables Tables which can be used for key optimization
4167
@param sargables IN/OUT Array of found sargable candidates
4170
If field items f1 and f2 belong to the same multiple equality and
4171
a key is added for f1, the the same key is added for f2.
4174
*key_fields is incremented if we stored a key in the array
4178
add_key_equal_fields(KEY_FIELD **key_fields, uint32_t and_level,
4179
Item_func *cond, Item_field *field_item,
4180
bool eq_func, Item **val,
4181
uint32_t num_values, table_map usable_tables,
4182
SARGABLE_PARAM **sargables)
4184
Field *field= field_item->field;
4185
add_key_field(key_fields, and_level, cond, field,
4186
eq_func, val, num_values, usable_tables, sargables);
4187
Item_equal *item_equal= field_item->item_equal;
4191
Add to the set of possible key values every substitution of
4192
the field for an equal field included into item_equal
4194
Item_equal_iterator it(*item_equal);
4196
while ((item= it++))
4198
if (!field->eq(item->field))
4200
add_key_field(key_fields, and_level, cond, item->field,
4201
eq_func, val, num_values, usable_tables,
4209
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint32_t *and_level,
4210
COND *cond, table_map usable_tables,
4211
SARGABLE_PARAM **sargables)
4213
if (cond->type() == Item_func::COND_ITEM)
4215
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
4216
KEY_FIELD *org_key_fields= *key_fields;
4218
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
4222
add_key_fields(join, key_fields, and_level, item, usable_tables,
4224
for (; org_key_fields != *key_fields ; org_key_fields++)
4225
org_key_fields->level= *and_level;
4230
add_key_fields(join, key_fields, and_level, li++, usable_tables,
4235
KEY_FIELD *start_key_fields= *key_fields;
4237
add_key_fields(join, key_fields, and_level, item, usable_tables,
4239
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
4240
*key_fields,++(*and_level));
4247
Subquery optimization: Conditions that are pushed down into subqueries
4248
are wrapped into Item_func_trig_cond. We process the wrapped condition
4249
but need to set cond_guard for KEYUSE elements generated from it.
4252
if (cond->type() == Item::FUNC_ITEM &&
4253
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
4255
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
4256
if (!join->group_list && !join->order &&
4258
join->unit->item->substype() == Item_subselect::IN_SUBS &&
4259
!join->unit->is_union())
4261
KEY_FIELD *save= *key_fields;
4262
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
4264
// Indicate that this ref access candidate is for subquery lookup:
4265
for (; save != *key_fields; save++)
4266
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
4272
/* If item is of type 'field op field/constant' add it to key_fields */
4273
if (cond->type() != Item::FUNC_ITEM)
4275
Item_func *cond_func= (Item_func*) cond;
4276
switch (cond_func->select_optimize()) {
4277
case Item_func::OPTIMIZE_NONE:
4279
case Item_func::OPTIMIZE_KEY:
4283
if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
4284
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4286
values= cond_func->arguments()+1;
4287
if (cond_func->functype() == Item_func::NE_FUNC &&
4288
cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4289
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4291
assert(cond_func->functype() != Item_func::IN_FUNC ||
4292
cond_func->argument_count() != 2);
4293
add_key_equal_fields(key_fields, *and_level, cond_func,
4294
(Item_field*) (cond_func->key_item()->real_item()),
4296
cond_func->argument_count()-1,
4297
usable_tables, sargables);
4299
if (cond_func->functype() == Item_func::BETWEEN)
4301
values= cond_func->arguments();
4302
for (uint32_t i= 1 ; i < cond_func->argument_count() ; i++)
4304
Item_field *field_item;
4305
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
4307
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
4309
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
4310
add_key_equal_fields(key_fields, *and_level, cond_func,
4311
field_item, 0, values, 1, usable_tables,
4318
case Item_func::OPTIMIZE_OP:
4320
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
4321
cond_func->functype() == Item_func::EQUAL_FUNC);
4323
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4324
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4326
add_key_equal_fields(key_fields, *and_level, cond_func,
4327
(Item_field*) (cond_func->arguments()[0])->real_item(),
4329
cond_func->arguments()+1, 1, usable_tables,
4332
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4333
cond_func->functype() != Item_func::LIKE_FUNC &&
4334
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
4336
add_key_equal_fields(key_fields, *and_level, cond_func,
4337
(Item_field*) (cond_func->arguments()[1])->real_item(),
4339
cond_func->arguments(),1,usable_tables,
4344
case Item_func::OPTIMIZE_NULL:
4345
/* column_name IS [NOT] NULL */
4346
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4347
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4349
Item *tmp=new Item_null;
4350
if (unlikely(!tmp)) // Should never be true
4352
add_key_equal_fields(key_fields, *and_level, cond_func,
4353
(Item_field*) (cond_func->arguments()[0])->real_item(),
4354
cond_func->functype() == Item_func::ISNULL_FUNC,
4355
&tmp, 1, usable_tables, sargables);
4358
case Item_func::OPTIMIZE_EQUAL:
4359
Item_equal *item_equal= (Item_equal *) cond;
4360
Item *const_item= item_equal->get_const();
4361
Item_equal_iterator it(*item_equal);
4366
For each field field1 from item_equal consider the equality
4367
field1=const_item as a condition allowing an index access of the table
4368
with field1 by the keys value of field1.
4370
while ((item= it++))
4372
add_key_field(key_fields, *and_level, cond_func, item->field,
4373
true, &const_item, 1, usable_tables, sargables);
4379
Consider all pairs of different fields included into item_equal.
4380
For each of them (field1, field1) consider the equality
4381
field1=field2 as a condition allowing an index access of the table
4382
with field1 by the keys value of field2.
4384
Item_equal_iterator fi(*item_equal);
4385
while ((item= fi++))
4387
Field *field= item->field;
4388
while ((item= it++))
4390
if (!field->eq(item->field))
4392
add_key_field(key_fields, *and_level, cond_func, field,
4393
true, (Item **) &item, 1, usable_tables,
4405
506
Add all keys with uses 'field' for some keypart.
4407
508
If field->and_level != and_level then only mark key_part as const_part.
4411
max_part_bit(key_part_map bits)
510
uint32_t max_part_bit(key_part_map bits)
4414
513
for (found=0; bits & 1 ; found++,bits>>=1) ;
4419
add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
4421
Field *field=key_field->field;
4422
Table *form= field->table;
4425
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
4427
for (uint32_t key= 0 ; key < form->sizeKeys() ; key++)
4429
if (!(form->keys_in_use_for_query.is_set(key)))
4432
uint32_t key_parts= (uint) form->key_info[key].key_parts;
4433
for (uint32_t part=0 ; part < key_parts ; part++)
4435
if (field->eq(form->key_info[key].key_part[part].field))
4437
keyuse.table= field->table;
4438
keyuse.val = key_field->val;
4440
keyuse.keypart=part;
4441
keyuse.keypart_map= (key_part_map) 1 << part;
4442
keyuse.used_tables=key_field->val->used_tables();
4443
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
4444
keyuse.null_rejecting= key_field->null_rejecting;
4445
keyuse.cond_guard= key_field->cond_guard;
4446
keyuse.sj_pred_no= key_field->sj_pred_no;
4447
insert_dynamic(keyuse_array,(unsigned char*) &keyuse);
4455
sort_keyuse(KEYUSE *a,KEYUSE *b)
517
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)
4458
if (a->table->tablenr != b->table->tablenr)
4459
return (int) (a->table->tablenr - b->table->tablenr);
4460
if (a->key != b->key)
4461
return (int) (a->key - b->key);
4462
if (a->keypart != b->keypart)
4463
return (int) (a->keypart - b->keypart);
520
if (a->getTable()->tablenr != b->getTable()->tablenr)
521
return static_cast<int>((a->getTable()->tablenr - b->getTable()->tablenr));
522
if (a->getKey() != b->getKey())
523
return static_cast<int>((a->getKey() - b->getKey()));
524
if (a->getKeypart() != b->getKeypart())
525
return static_cast<int>((a->getKeypart() - b->getKeypart()));
4464
526
// Place const values before other ones
4465
if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
4466
test((b->used_tables & ~OUTER_REF_TABLE_BIT))))
527
if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -
528
test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))
4468
530
/* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
4469
return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
4470
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
4475
Add to KEY_FIELD array all 'ref' access candidates within nested join.
4477
This function populates KEY_FIELD array with entries generated from the
4478
ON condition of the given nested join, and does the same for nested joins
4479
contained within this nested join.
4481
@param[in] nested_join_table Nested join pseudo-table to process
4482
@param[in,out] end End of the key field array
4483
@param[in,out] and_level And-level
4484
@param[in,out] sargables Array of found sargable candidates
4488
We can add accesses to the tables that are direct children of this nested
4489
join (1), and are not inner tables w.r.t their neighbours (2).
4491
Example for #1 (outer brackets pair denotes nested join this function is
4494
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
4498
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
4500
In examples 1-2 for condition cond, we can add 'ref' access candidates to
4504
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
4506
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
4509
static void add_key_fields_for_nj(JOIN *join, TableList *nested_join_table,
4510
KEY_FIELD **end, uint32_t *and_level,
4511
SARGABLE_PARAM **sargables)
4513
List_iterator<TableList> li(nested_join_table->nested_join->join_list);
4514
List_iterator<TableList> li2(nested_join_table->nested_join->join_list);
4515
bool have_another = false;
4516
table_map tables= 0;
4518
assert(nested_join_table->nested_join);
4520
while ((table= li++) || (have_another && (li=li2, have_another=false,
4523
if (table->nested_join)
4525
if (!table->on_expr)
4527
/* It's a semi-join nest. Walk into it as if it wasn't a nest */
4530
li= List_iterator<TableList>(table->nested_join->join_list);
4533
add_key_fields_for_nj(join, table, end, and_level, sargables);
4536
if (!table->on_expr)
4537
tables |= table->table->map;
4539
if (nested_join_table->on_expr)
4540
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
531
return static_cast<int>(((a->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) -
532
(b->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)));
4546
537
Update keyuse array with all possible keys we can use to fetch rows.
4549
@param[out] keyuse Put here ordered array of KEYUSE structures
540
@param[out] keyuse Put here ordered array of KeyUse structures
4550
541
@param join_tab Array in tablenr_order
4551
542
@param tables Number of tables in join
4552
543
@param cond WHERE condition (note that the function analyzes
4805
788
/* Intersect the keys of all group fields. */
4806
789
cur_item= indexed_fields_it++;
4807
possible_keys.merge(cur_item->field->part_of_key);
790
possible_keys|= cur_item->field->part_of_key;
4808
791
while ((cur_item= indexed_fields_it++))
4810
possible_keys.intersect(cur_item->field->part_of_key);
4813
if (!possible_keys.is_clear_all())
4814
join_tab->const_keys.merge(possible_keys);
4818
/*****************************************************************************
4819
Go through all combinations of not marked tables and find the one
4820
which uses least records
4821
*****************************************************************************/
4823
/** Save const tables first as used tables. */
4826
set_position(JOIN *join,uint32_t idx,JOIN_TAB *table,KEYUSE *key)
4828
join->positions[idx].table= table;
4829
join->positions[idx].key=key;
4830
join->positions[idx].records_read=1.0; /* This is a const table */
4831
join->positions[idx].ref_depend_map= 0;
4833
/* Move the const table as down as possible in best_ref */
4834
JOIN_TAB **pos=join->best_ref+idx+1;
4835
JOIN_TAB *next=join->best_ref[idx];
4836
for (;next != table ; pos++)
4838
JOIN_TAB *tmp=pos[0];
4842
join->best_ref[idx]=table;
4847
Given a semi-join nest, find out which of the IN-equalities are bound
4850
get_bound_sj_equalities()
4851
sj_nest Semi-join nest
4852
remaining_tables Tables that are not yet bound
4855
Given a semi-join nest, find out which of the IN-equalities have their
4856
left part expression bound (i.e. the said expression doesn't refer to
4857
any of remaining_tables and can be evaluated).
4860
Bitmap of bound IN-equalities.
4863
uint64_t get_bound_sj_equalities(TableList *sj_nest,
4864
table_map remaining_tables)
4866
List_iterator<Item> li(sj_nest->nested_join->sj_outer_expr_list);
4870
while ((item= li++))
4873
Q: should this take into account equality propagation and how?
4874
A: If e->outer_side is an Item_field, walk over the equality
4875
class and see if there is an element that is bound?
4876
(this is an optional feature)
4878
if (!(item->used_tables() & remaining_tables))
4888
Find the best access path for an extension of a partial execution
4889
plan and add this path to the plan.
4891
The function finds the best access path to table 's' from the passed
4892
partial plan where an access path is the general term for any means to
4893
access the data in 's'. An access path may use either an index or a scan,
4894
whichever is cheaper. The input partial plan is passed via the array
4895
'join->positions' of length 'idx'. The chosen access method for 's' and its
4896
cost are stored in 'join->positions[idx]'.
4898
@param join pointer to the structure providing all context info
4900
@param s the table to be joined by the function
4901
@param thd thread for the connection that submitted the query
4902
@param remaining_tables set of tables not included into the partial plan yet
4903
@param idx the length of the partial plan
4904
@param record_count estimate for the number of records returned by the
4906
@param read_time the cost of the partial plan
4913
best_access_path(JOIN *join,
4916
table_map remaining_tables,
4918
double record_count,
4919
double read_time __attribute__((unused)))
4921
KEYUSE *best_key= 0;
4922
uint32_t best_max_key_part= 0;
4923
bool found_constraint= 0;
4924
double best= DBL_MAX;
4925
double best_time= DBL_MAX;
4926
double records= DBL_MAX;
4927
table_map best_ref_depends_map= 0;
4930
uint32_t best_is_sj_inside_out= 0;
4933
{ /* Use key if possible */
4934
Table *table= s->table;
4935
KEYUSE *keyuse,*start_key=0;
4936
double best_records= DBL_MAX;
4937
uint32_t max_key_part=0;
4938
uint64_t bound_sj_equalities= 0;
4939
bool try_sj_inside_out= false;
4941
Discover the bound equalites. We need to do this, if
4942
1. The next table is an SJ-inner table, and
4943
2. It is the first table from that semijoin, and
4944
3. We're not within a semi-join range (i.e. all semi-joins either have
4945
all or none of their tables in join_table_map), except
4946
s->emb_sj_nest (which we've just entered).
4947
3. All correlation references from this sj-nest are bound
4949
if (s->emb_sj_nest && // (1)
4950
s->emb_sj_nest->sj_in_exprs < 64 &&
4951
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
4952
s->emb_sj_nest->sj_inner_tables) && // (2)
4953
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
4954
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
4956
/* This table is an InsideOut scan candidate */
4957
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
4959
try_sj_inside_out= true;
4962
/* Test how we can use keys */
4963
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
4964
for (keyuse=s->keyuse ; keyuse->table == table ;)
4966
key_part_map found_part= 0;
4967
table_map found_ref= 0;
4968
uint32_t key= keyuse->key;
4969
KEY *keyinfo= table->key_info+key;
4970
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
4971
key_part_map const_part= 0;
4972
/* The or-null keypart in ref-or-null access: */
4973
key_part_map ref_or_null_part= 0;
4975
/* Calculate how many key segments of the current key we can use */
4977
uint64_t handled_sj_equalities=0;
4978
key_part_map sj_insideout_map= 0;
4980
do /* For each keypart */
4982
uint32_t keypart= keyuse->keypart;
4983
table_map best_part_found_ref= 0;
4984
double best_prev_record_reads= DBL_MAX;
4986
do /* For each way to access the keypart */
4990
if 1. expression doesn't refer to forward tables
4991
2. we won't get two ref-or-null's
4993
if (!(remaining_tables & keyuse->used_tables) &&
4994
!(ref_or_null_part && (keyuse->optimize &
4995
KEY_OPTIMIZE_REF_OR_NULL)))
4997
found_part|= keyuse->keypart_map;
4998
if (!(keyuse->used_tables & ~join->const_table_map))
4999
const_part|= keyuse->keypart_map;
5001
double tmp2= prev_record_reads(join, idx, (found_ref |
5002
keyuse->used_tables));
5003
if (tmp2 < best_prev_record_reads)
5005
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
5006
best_prev_record_reads= tmp2;
5008
if (rec > keyuse->ref_table_rows)
5009
rec= keyuse->ref_table_rows;
5011
If there is one 'key_column IS NULL' expression, we can
5012
use this ref_or_null optimisation of this field
5014
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
5015
ref_or_null_part |= keyuse->keypart_map;
5018
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
5020
if (!(remaining_tables & keyuse->used_tables))
5021
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
5024
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
5025
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
5030
} while (keyuse->table == table && keyuse->key == key &&
5031
keyuse->keypart == keypart);
5032
found_ref|= best_part_found_ref;
5033
} while (keyuse->table == table && keyuse->key == key);
5036
Assume that that each key matches a proportional part of table.
5038
if (!found_part && !handled_sj_equalities)
5039
continue; // Nothing usable found
5041
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
5042
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
5044
bool sj_inside_out_scan= false;
5046
found_constraint= 1;
5048
Check if InsideOut scan is applicable:
5049
1. All IN-equalities are either "bound" or "handled"
5050
2. Index keyparts are
5053
if (try_sj_inside_out &&
5054
table->covering_keys.is_set(key) &&
5055
(handled_sj_equalities | bound_sj_equalities) == // (1)
5056
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
5058
uint32_t n_fixed_parts= max_part_bit(found_part);
5059
if (n_fixed_parts != keyinfo->key_parts &&
5060
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
5061
PREV_BITS(uint, keyinfo->key_parts))
5064
Not all parts are fixed. Produce bitmap of remaining bits and
5065
check if all of them are covered.
5067
sj_inside_out_scan= true;
5071
It's a confluent ref scan.
5073
That is, all found KEYUSE elements refer to IN-equalities,
5074
and there is really no ref access because there is no
5075
t.keypart0 = {bound expression}
5077
Calculate the cost of complete loose index scan.
5079
records= (double)s->table->file->stats.records;
5081
/* The cost is entire index scan cost (divided by 2) */
5082
best_time= s->table->file->index_only_read_time(key, records);
5084
/* Now figure how many different keys we will get */
5086
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
5087
records= records / rpc;
5094
Check if we found full key
5096
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
5099
max_key_part= UINT32_MAX;
5100
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
5102
tmp = prev_record_reads(join, idx, found_ref);
5108
{ /* We found a const key */
5110
ReuseRangeEstimateForRef-1:
5111
We get here if we've found a ref(const) (c_i are constants):
5112
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
5114
If range optimizer was able to construct a "range"
5115
access on this index, then its condition "quick_cond" was
5116
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
5117
from the range optimizer.
5119
Proof of (*): By properties of range and ref optimizers
5120
quick_cond will be equal or tighther than ref_const_cond.
5121
ref_const_cond already covers "smallest" possible interval -
5122
a singlepoint interval over all keyparts. Therefore,
5123
quick_cond is equivalent to ref_const_cond (if it was an
5124
empty interval we wouldn't have got here).
5126
if (table->quick_keys.is_set(key))
5127
records= (double) table->quick_rows[key];
5130
/* quick_range couldn't use key! */
5131
records= (double) s->records/rec;
5136
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
5137
{ /* Prefer longer keys */
5139
((double) s->records / (double) rec *
5141
((double) (table->s->max_key_length-keyinfo->key_length) /
5142
(double) table->s->max_key_length)));
5144
records=2.0; /* Can't be as good as a unique */
5147
ReuseRangeEstimateForRef-2: We get here if we could not reuse
5148
E(#rows) from range optimizer. Make another try:
5150
If range optimizer produced E(#rows) for a prefix of the ref
5151
access we're considering, and that E(#rows) is lower then our
5152
current estimate, make an adjustment. The criteria of when we
5153
can make an adjustment is a special case of the criteria used
5154
in ReuseRangeEstimateForRef-3.
5156
if (table->quick_keys.is_set(key) &&
5157
const_part & (1 << table->quick_key_parts[key]) &&
5158
table->quick_n_ranges[key] == 1 &&
5159
records > (double) table->quick_rows[key])
5161
records= (double) table->quick_rows[key];
5164
/* Limit the number of matched rows */
5166
set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key);
5167
if (table->covering_keys.is_set(key))
5169
/* we can use only index tree */
5170
tmp= record_count * table->file->index_only_read_time(key, tmp);
5173
tmp= record_count*cmin(tmp,s->worst_seeks);
5179
Use as much key-parts as possible and a uniq key is better
5180
than a not unique key
5181
Set tmp to (previous record count) * (records / combination)
5183
if ((found_part & 1) &&
5184
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
5185
found_part == PREV_BITS(uint,keyinfo->key_parts)))
5187
max_key_part= max_part_bit(found_part);
5189
ReuseRangeEstimateForRef-3:
5190
We're now considering a ref[or_null] access via
5191
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
5192
(same-as-above but with one cond replaced
5193
with "t.keypart_i IS NULL")] (**)
5195
Try re-using E(#rows) from "range" optimizer:
5196
We can do so if "range" optimizer used the same intervals as
5197
in (**). The intervals used by range optimizer may be not
5198
available at this point (as "range" access might have choosen to
5199
create quick select over another index), so we can't compare
5200
them to (**). We'll make indirect judgements instead.
5201
The sufficient conditions for re-use are:
5202
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
5203
this is not satisfied we have no way to know which ranges
5204
will be actually scanned by 'ref' until we execute the
5206
(C2) max #key parts in 'range' access == K == max_key_part (this
5207
is apparently a necessary requirement)
5209
We also have a property that "range optimizer produces equal or
5210
tighter set of scan intervals than ref(const) optimizer". Each
5211
of the intervals in (**) are "tightest possible" intervals when
5212
one limits itself to using keyparts 1..K (which we do in #2).
5213
From here it follows that range access used either one, or
5214
both of the (I1) and (I2) intervals:
5216
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
5217
(same-as-above but with one cond replaced
5218
with "t.keypart_i IS NULL") (I2)
5220
The remaining part is to exclude the situation where range
5221
optimizer used one interval while we're considering
5222
ref-or-null and looking for estimate for two intervals. This
5223
is done by last limitation:
5225
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
5227
if (table->quick_keys.is_set(key) && !found_ref && //(C1)
5228
table->quick_key_parts[key] == max_key_part && //(C2)
5229
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
5231
tmp= records= (double) table->quick_rows[key];
5235
/* Check if we have statistic about the distribution */
5236
if ((records= keyinfo->rec_per_key[max_key_part-1]))
5239
Fix for the case where the index statistics is too
5241
(1) We're considering ref(const) and there is quick select
5243
(2) and that quick select uses more keyparts (i.e. it will
5244
scan equal/smaller interval then this ref(const))
5245
(3) and E(#rows) for quick select is higher then our
5248
We'll use E(#rows) from quick select.
5250
Q: Why do we choose to use 'ref'? Won't quick select be
5251
cheaper in some cases ?
5252
TODO: figure this out and adjust the plan choice if needed.
5254
if (!found_ref && table->quick_keys.is_set(key) && // (1)
5255
table->quick_key_parts[key] > max_key_part && // (2)
5256
records < (double)table->quick_rows[key]) // (3)
5257
records= (double)table->quick_rows[key];
5264
Assume that the first key part matches 1% of the file
5265
and that the whole key matches 10 (duplicates) or 1
5267
Assume also that more key matches proportionally more
5269
This gives the formula:
5270
records = (x * (b-a) + a*c-b)/(c-1)
5272
b = records matched by whole key
5273
a = records matched by first key part (1% of all records?)
5274
c = number of key parts in key
5275
x = used key parts (1 <= x <= c)
5278
if (!(rec_per_key=(double)
5279
keyinfo->rec_per_key[keyinfo->key_parts-1]))
5280
rec_per_key=(double) s->records/rec+1;
5284
else if (rec_per_key/(double) s->records >= 0.01)
5288
double a=s->records*0.01;
5289
if (keyinfo->key_parts > 1)
5290
tmp= (max_key_part * (rec_per_key - a) +
5291
a*keyinfo->key_parts - rec_per_key)/
5292
(keyinfo->key_parts-1);
5295
set_if_bigger(tmp,1.0);
5297
records = (ulong) tmp;
5300
if (ref_or_null_part)
5302
/* We need to do two key searches to find key */
5308
ReuseRangeEstimateForRef-4: We get here if we could not reuse
5309
E(#rows) from range optimizer. Make another try:
5311
If range optimizer produced E(#rows) for a prefix of the ref
5312
access we're considering, and that E(#rows) is lower then our
5313
current estimate, make the adjustment.
5315
The decision whether we can re-use the estimate from the range
5316
optimizer is the same as in ReuseRangeEstimateForRef-3,
5317
applied to first table->quick_key_parts[key] key parts.
5319
if (table->quick_keys.is_set(key) &&
5320
table->quick_key_parts[key] <= max_key_part &&
5321
const_part & (1 << table->quick_key_parts[key]) &&
5322
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
5323
const_part) ? 1 : 0) &&
5324
records > (double) table->quick_rows[key])
5326
tmp= records= (double) table->quick_rows[key];
5330
/* Limit the number of matched rows */
5331
set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key);
5332
if (table->covering_keys.is_set(key))
5334
/* we can use only index tree */
5335
tmp= record_count * table->file->index_only_read_time(key, tmp);
5338
tmp= record_count * cmin(tmp,s->worst_seeks);
5341
tmp= best_time; // Do nothing
5344
if (sj_inside_out_scan && !start_key)
5352
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
5354
best_time= tmp + records/(double) TIME_FOR_COMPARE;
5356
best_records= records;
5357
best_key= start_key;
5358
best_max_key_part= max_key_part;
5359
best_ref_depends_map= found_ref;
5360
best_is_sj_inside_out= sj_inside_out_scan;
5363
records= best_records;
5367
Don't test table scan if it can't be better.
5368
Prefer key lookup if we would use the same key for scanning.
5370
Don't do a table scan on InnoDB tables, if we can read the used
5371
parts of the row from any of the used index.
5372
This is because table scans uses index and we would not win
5373
anything by using a table scan.
5375
A word for word translation of the below if-statement in sergefp's
5376
understanding: we check if we should use table scan if:
5377
(1) The found 'ref' access produces more records than a table scan
5378
(or index scan, or quick select), or 'ref' is more expensive than
5380
(2) This doesn't hold: the best way to perform table scan is to to perform
5381
'range' access using index IDX, and the best way to perform 'ref'
5382
access is to use the same index IDX, with the same or more key parts.
5383
(note: it is not clear how this rule is/should be extended to
5384
index_merge quick selects)
5385
(3) See above note about InnoDB.
5386
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
5387
path, but there is no quick select)
5388
If the condition in the above brackets holds, then the only possible
5389
"table scan" access method is ALL/index (there is no quick select).
5390
Since we have a 'ref' access path, and FORCE INDEX instructs us to
5391
choose it over ALL/index, there is no need to consider a full table
5394
if ((records >= s->found_records || best > s->read_time) && // (1)
5395
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
5396
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
5397
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
5398
! s->table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
5399
!(s->table->force_index && best_key && !s->quick)) // (4)
5400
{ // Check full join
5401
ha_rows rnd_records= s->found_records;
5403
If there is a filtering condition on the table (i.e. ref analyzer found
5404
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
5405
preceding this table in the join order we're now considering), then
5406
assume that 25% of the rows will be filtered out by this condition.
5408
This heuristic is supposed to force tables used in exprZ to be before
5409
this table in join order.
5411
if (found_constraint)
5412
rnd_records-= rnd_records/4;
5415
If applicable, get a more accurate estimate. Don't use the two
5418
if (s->table->quick_condition_rows != s->found_records)
5419
rnd_records= s->table->quick_condition_rows;
5422
Range optimizer never proposes a RANGE if it isn't better
5423
than FULL: so if RANGE is present, it's always preferred to FULL.
5424
Here we estimate its cost.
5430
- read record range through 'quick'
5431
- skip rows which does not satisfy WHERE constraints
5433
We take into account possible use of join cache for ALL/index
5434
access (see first else-branch below), but we don't take it into
5435
account here for range/index_merge access. Find out why this is so.
5438
(s->quick->read_time +
5439
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
5443
/* Estimate cost of reading table. */
5444
tmp= s->table->file->scan_time();
5445
if (s->table->map & join->outer_join) // Can't use join cache
5448
For each record we have to:
5449
- read the whole table record
5450
- skip rows which does not satisfy join condition
5454
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
5458
/* We read the table as many times as join buffer becomes full. */
5459
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
5461
(double) thd->variables.join_buff_size));
5463
We don't make full cartesian product between rows in the scanned
5464
table and existing records because we skip all rows from the
5465
scanned table, which does not satisfy join condition when
5466
we read the table (see flush_cached_records for details). Here we
5467
take into account cost to read and skip these records.
5469
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
5474
We estimate the cost of evaluating WHERE clause for found records
5475
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
5476
tmp give us total cost of using Table SCAN
5478
if (best == DBL_MAX ||
5479
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
5480
best + record_count/(double) TIME_FOR_COMPARE*records))
5483
If the table has a range (s->quick is set) make_join_select()
5484
will ensure that this will be used
5487
records= rows2double(rnd_records);
5489
/* range/index_merge/ALL/index access method are "independent", so: */
5490
best_ref_depends_map= 0;
5491
best_is_sj_inside_out= false;
5495
/* Update the cost information for the current partial plan */
5496
join->positions[idx].records_read= records;
5497
join->positions[idx].read_time= best;
5498
join->positions[idx].key= best_key;
5499
join->positions[idx].table= s;
5500
join->positions[idx].ref_depend_map= best_ref_depends_map;
5501
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
5504
idx == join->const_tables &&
5505
s->table == join->sort_by_table &&
5506
join->unit->select_limit_cnt >= records)
5507
join->sort_by_table= (Table*) 1; // Must use temporary table
5514
Selects and invokes a search strategy for an optimal query plan.
5516
The function checks user-configurable parameters that control the search
5517
strategy for an optimal plan, selects the search method and then invokes
5518
it. Each specific optimization procedure stores the final optimal plan in
5519
the array 'join->best_positions', and the cost of the plan in
5522
@param join pointer to the structure providing all context info for
5524
@param join_tables set of the tables in the query
5527
'MAX_TABLES+2' denotes the old implementation of find_best before
5528
the greedy version. Will be removed when greedy_search is approved.
5537
choose_plan(JOIN *join, table_map join_tables)
5539
uint32_t search_depth= join->thd->variables.optimizer_search_depth;
5540
uint32_t prune_level= join->thd->variables.optimizer_prune_level;
5541
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
5543
join->cur_embedding_map= 0;
5544
reset_nj_counters(join->join_list);
5546
if (SELECT_STRAIGHT_JOIN option is set)
5547
reorder tables so dependent tables come after tables they depend
5548
on, otherwise keep tables in the order they were specified in the query
5550
Apply heuristic: pre-sort all access plans with respect to the number of
5553
my_qsort(join->best_ref + join->const_tables,
5554
join->tables - join->const_tables, sizeof(JOIN_TAB*),
5555
straight_join ? join_tab_cmp_straight : join_tab_cmp);
5556
join->cur_emb_sj_nests= 0;
5559
optimize_straight_join(join, join_tables);
5563
if (search_depth == MAX_TABLES+2)
5565
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
5566
the greedy version. Will be removed when greedy_search is approved.
5568
join->best_read= DBL_MAX;
5569
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
5574
if (search_depth == 0)
5575
/* Automatically determine a reasonable value for 'search_depth' */
5576
search_depth= determine_search_depth(join);
5577
if (greedy_search(join, join_tables, search_depth, prune_level))
5583
Store the cost of this query into a user variable
5584
Don't update last_query_cost for statements that are not "flat joins" :
5585
i.e. they have subqueries, unions or call stored procedures.
5586
TODO: calculate a correct cost for a query with subqueries and UNIONs.
5588
if (join->thd->lex->is_single_level_stmt())
5589
join->thd->status_var.last_query_cost= join->best_read;
5595
Compare two JOIN_TAB objects based on the number of accessed records.
5597
@param ptr1 pointer to first JOIN_TAB object
5598
@param ptr2 pointer to second JOIN_TAB object
793
possible_keys&= cur_item->field->part_of_key;
796
if (possible_keys.any())
797
join_tab->const_keys|= possible_keys;
801
Compare two JoinTable objects based on the number of accessed records.
803
@param ptr1 pointer to first JoinTable object
804
@param ptr2 pointer to second JoinTable object
5601
807
The order relation implemented by join_tab_cmp() is not transitive,
5655
Heuristic procedure to automatically guess a reasonable degree of
5656
exhaustiveness for the greedy search procedure.
5658
The procedure estimates the optimization time and selects a search depth
5659
big enough to result in a near-optimal QEP, that doesn't take too long to
5660
find. If the number of tables in the query exceeds some constant, then
5661
search_depth is set to this constant.
5663
@param join pointer to the structure providing all context info for
5667
This is an extremely simplistic implementation that serves as a stub for a
5668
more advanced analysis of the join. Ideally the search depth should be
5669
determined by learning from previous query optimizations, because it will
5670
depend on the CPU power (and other factors).
5673
this value should be determined dynamically, based on statistics:
5674
uint32_t max_tables_for_exhaustive_opt= 7;
5677
this value could be determined by some mapping of the form:
5678
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5681
A positive integer that specifies the search depth (and thus the
5682
exhaustiveness) of the depth-first search algorithm used by
5687
determine_search_depth(JOIN *join)
5689
uint32_t table_count= join->tables - join->const_tables;
5690
uint32_t search_depth;
5691
/* TODO: this value should be determined dynamically, based on statistics: */
5692
uint32_t max_tables_for_exhaustive_opt= 7;
5694
if (table_count <= max_tables_for_exhaustive_opt)
5695
search_depth= table_count+1; // use exhaustive for small number of tables
5698
TODO: this value could be determined by some mapping of the form:
5699
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5701
search_depth= max_tables_for_exhaustive_opt; // use greedy search
5703
return search_depth;
5708
Select the best ways to access the tables in a query without reordering them.
5710
Find the best access paths for each query table and compute their costs
5711
according to their order in the array 'join->best_ref' (thus without
5712
reordering the join tables). The function calls sequentially
5713
'best_access_path' for each table in the query to select the best table
5714
access method. The final optimal plan is stored in the array
5715
'join->best_positions', and the corresponding cost in 'join->best_read'.
5717
@param join pointer to the structure providing all context info for
5719
@param join_tables set of the tables in the query
5722
This function can be applied to:
5723
- queries with STRAIGHT_JOIN
5724
- internally to compute the cost of an arbitrary QEP
5726
Thus 'optimize_straight_join' can be used at any stage of the query
5727
optimization process to finalize a QEP as it is.
5731
optimize_straight_join(JOIN *join, table_map join_tables)
5734
uint32_t idx= join->const_tables;
5735
double record_count= 1.0;
5736
double read_time= 0.0;
5738
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
5740
/* Find the best access method from 's' to the current partial plan */
5741
advance_sj_state(join_tables, s);
5742
best_access_path(join, s, join->thd, join_tables, idx,
5743
record_count, read_time);
5744
/* compute the cost of the new plan extended with 's' */
5745
record_count*= join->positions[idx].records_read;
5746
read_time+= join->positions[idx].read_time;
5747
join_tables&= ~(s->table->map);
5751
read_time+= record_count / (double) TIME_FOR_COMPARE;
5752
if (join->sort_by_table &&
5753
join->sort_by_table != join->positions[join->const_tables].table->table)
5754
read_time+= record_count; // We have to make a temp table
5755
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
5756
join->best_read= read_time;
5761
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
5763
The search procedure uses a hybrid greedy/exhaustive search with controlled
5764
exhaustiveness. The search is performed in N = card(remaining_tables)
5765
steps. Each step evaluates how promising is each of the unoptimized tables,
5766
selects the most promising table, and extends the current partial QEP with
5767
that table. Currenly the most 'promising' table is the one with least
5768
expensive extension.\
5770
There are two extreme cases:
5771
-# When (card(remaining_tables) < search_depth), the estimate finds the
5772
best complete continuation of the partial QEP. This continuation can be
5773
used directly as a result of the search.
5774
-# When (search_depth == 1) the 'best_extension_by_limited_search'
5775
consideres the extension of the current QEP with each of the remaining
5778
All other cases are in-between these two extremes. Thus the parameter
5779
'search_depth' controlls the exhaustiveness of the search. The higher the
5780
value, the longer the optimizaton time and possibly the better the
5781
resulting plan. The lower the value, the fewer alternative plans are
5782
estimated, but the more likely to get a bad QEP.
5784
All intermediate and final results of the procedure are stored in 'join':
5785
- join->positions : modified for every partial QEP that is explored
5786
- join->best_positions: modified for the current best complete QEP
5787
- join->best_read : modified for the current best complete QEP
5788
- join->best_ref : might be partially reordered
5790
The final optimal plan is stored in 'join->best_positions', and its
5791
corresponding cost in 'join->best_read'.
5794
The following pseudocode describes the algorithm of 'greedy_search':
5797
procedure greedy_search
5798
input: remaining_tables
5803
(t, a) = best_extension(pplan, remaining_tables);
5804
pplan = concat(pplan, (t, a));
5805
remaining_tables = remaining_tables - t;
5806
} while (remaining_tables != {})
5811
where 'best_extension' is a placeholder for a procedure that selects the
5812
most "promising" of all tables in 'remaining_tables'.
5813
Currently this estimate is performed by calling
5814
'best_extension_by_limited_search' to evaluate all extensions of the
5815
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
5816
mainly depends on that of 'best_extension_by_limited_search'.
5819
If 'best_extension()' == 'best_extension_by_limited_search()', then the
5820
worst-case complexity of this algorithm is <=
5821
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
5822
complexity of greedy_search is O(N!).
5825
In the future, 'greedy_search' might be extended to support other
5826
implementations of 'best_extension', e.g. some simpler quadratic procedure.
5828
@param join pointer to the structure providing all context info
5830
@param remaining_tables set of tables not included into the partial plan yet
5831
@param search_depth controlls the exhaustiveness of the search
5832
@param prune_level the pruning heuristics that should be applied during
5842
greedy_search(JOIN *join,
5843
table_map remaining_tables,
5844
uint32_t search_depth,
5845
uint32_t prune_level)
5847
double record_count= 1.0;
5848
double read_time= 0.0;
5849
uint32_t idx= join->const_tables; // index into 'join->best_ref'
5851
uint32_t size_remain; // cardinality of remaining_tables
5853
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
5855
/* number of tables that remain to be optimized */
5856
size_remain= my_count_bits(remaining_tables);
5859
/* Find the extension of the current QEP with the lowest cost */
5860
join->best_read= DBL_MAX;
5861
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
5862
read_time, search_depth, prune_level))
5865
if (size_remain <= search_depth)
5868
'join->best_positions' contains a complete optimal extension of the
5869
current partial QEP.
5874
/* select the first table in the optimal extension as most promising */
5875
best_pos= join->best_positions[idx];
5876
best_table= best_pos.table;
5878
Each subsequent loop of 'best_extension_by_limited_search' uses
5879
'join->positions' for cost estimates, therefore we have to update its
5882
join->positions[idx]= best_pos;
5884
/* find the position of 'best_table' in 'join->best_ref' */
5886
JOIN_TAB *pos= join->best_ref[best_idx];
5887
while (pos && best_table != pos)
5888
pos= join->best_ref[++best_idx];
5889
assert((pos != NULL)); // should always find 'best_table'
5890
/* move 'best_table' at the first free position in the array of joins */
5891
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
5893
/* compute the cost of the new plan extended with 'best_table' */
5894
record_count*= join->positions[idx].records_read;
5895
read_time+= join->positions[idx].read_time;
5897
remaining_tables&= ~(best_table->table->map);
5905
Find a good, possibly optimal, query execution plan (QEP) by a possibly
5908
The procedure searches for the optimal ordering of the query tables in set
5909
'remaining_tables' of size N, and the corresponding optimal access paths to
5910
each table. The choice of a table order and an access path for each table
5911
constitutes a query execution plan (QEP) that fully specifies how to
5914
The maximal size of the found plan is controlled by the parameter
5915
'search_depth'. When search_depth == N, the resulting plan is complete and
5916
can be used directly as a QEP. If search_depth < N, the found plan consists
5917
of only some of the query tables. Such "partial" optimal plans are useful
5918
only as input to query optimization procedures, and cannot be used directly
5921
The algorithm begins with an empty partial plan stored in 'join->positions'
5922
and a set of N tables - 'remaining_tables'. Each step of the algorithm
5923
evaluates the cost of the partial plan extended by all access plans for
5924
each of the relations in 'remaining_tables', expands the current partial
5925
plan with the access plan that results in lowest cost of the expanded
5926
partial plan, and removes the corresponding relation from
5927
'remaining_tables'. The algorithm continues until it either constructs a
5928
complete optimal plan, or constructs an optimal plartial plan with size =
5931
The final optimal plan is stored in 'join->best_positions'. The
5932
corresponding cost of the optimal plan is in 'join->best_read'.
5935
The procedure uses a recursive depth-first search where the depth of the
5936
recursion (and thus the exhaustiveness of the search) is controlled by the
5937
parameter 'search_depth'.
5940
The pseudocode below describes the algorithm of
5941
'best_extension_by_limited_search'. The worst-case complexity of this
5942
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
5943
the complexity of greedy_search is O(N!).
5946
procedure best_extension_by_limited_search(
5947
pplan in, // in, partial plan of tables-joined-so-far
5948
pplan_cost, // in, cost of pplan
5949
remaining_tables, // in, set of tables not referenced in pplan
5950
best_plan_so_far, // in/out, best plan found so far
5951
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5952
search_depth) // in, maximum size of the plans being considered
5954
for each table T from remaining_tables
5956
// Calculate the cost of using table T as above
5957
cost = complex-series-of-calculations;
5959
// Add the cost to the cost so far.
5962
if (pplan_cost >= best_plan_so_far_cost)
5963
// pplan_cost already too great, stop search
5966
pplan= expand pplan by best_access_method;
5967
remaining_tables= remaining_tables - table T;
5968
if (remaining_tables is not an empty set
5972
best_extension_by_limited_search(pplan, pplan_cost,
5975
best_plan_so_far_cost,
5980
best_plan_so_far_cost= pplan_cost;
5981
best_plan_so_far= pplan;
5988
When 'best_extension_by_limited_search' is called for the first time,
5989
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
5990
The actual implementation provides a way to optionally use pruning
5991
heuristic (controlled by the parameter 'prune_level') to reduce the search
5992
space by skipping some partial plans.
5995
The parameter 'search_depth' provides control over the recursion
5996
depth, and thus the size of the resulting optimal plan.
5998
@param join pointer to the structure providing all context info
6000
@param remaining_tables set of tables not included into the partial plan yet
6001
@param idx length of the partial QEP in 'join->positions';
6002
since a depth-first search is used, also corresponds
6003
to the current depth of the search tree;
6004
also an index in the array 'join->best_ref';
6005
@param record_count estimate for the number of records returned by the
6007
@param read_time the cost of the best partial plan
6008
@param search_depth maximum depth of the recursion and thus size of the
6010
(0 < search_depth <= join->tables+1).
6011
@param prune_level pruning heuristics that should be applied during
6013
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
6022
best_extension_by_limited_search(JOIN *join,
6023
table_map remaining_tables,
6025
double record_count,
6027
uint32_t search_depth,
6028
uint32_t prune_level)
6030
THD *thd= join->thd;
6031
if (thd->killed) // Abort
6035
'join' is a partial plan with lower cost than the best plan so far,
6036
so continue expanding it further with the tables in 'remaining_tables'.
6039
double best_record_count= DBL_MAX;
6040
double best_read_time= DBL_MAX;
6042
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
6044
table_map real_table_bit= s->table->map;
6045
if ((remaining_tables & real_table_bit) &&
6046
!(remaining_tables & s->dependent) &&
6047
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6049
double current_record_count, current_read_time;
6050
advance_sj_state(remaining_tables, s);
6053
psergey-insideout-todo:
6054
when best_access_path() detects it could do an InsideOut scan or
6055
some other scan, have it return an insideout scan and a flag that
6056
requests to "fork" this loop iteration. (Q: how does that behave
6057
when the depth is insufficient??)
6059
/* Find the best access method from 's' to the current partial plan */
6060
best_access_path(join, s, thd, remaining_tables, idx,
6061
record_count, read_time);
6062
/* Compute the cost of extending the plan with 's' */
6063
current_record_count= record_count * join->positions[idx].records_read;
6064
current_read_time= read_time + join->positions[idx].read_time;
6066
/* Expand only partial plans with lower cost than the best QEP so far */
6067
if ((current_read_time +
6068
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
6070
restore_prev_nj_state(s);
6071
restore_prev_sj_state(remaining_tables, s);
6076
Prune some less promising partial plans. This heuristic may miss
6077
the optimal QEPs, thus it results in a non-exhaustive search.
6079
if (prune_level == 1)
6081
if (best_record_count > current_record_count ||
6082
best_read_time > current_read_time ||
6083
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
6085
if (best_record_count >= current_record_count &&
6086
best_read_time >= current_read_time &&
6087
/* TODO: What is the reasoning behind this condition? */
6088
(!(s->key_dependent & remaining_tables) ||
6089
join->positions[idx].records_read < 2.0))
6091
best_record_count= current_record_count;
6092
best_read_time= current_read_time;
6097
restore_prev_nj_state(s);
6098
restore_prev_sj_state(remaining_tables, s);
6103
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
6104
{ /* Recursively expand the current partial plan */
6105
std::swap(join->best_ref[idx], *pos);
6106
if (best_extension_by_limited_search(join,
6107
remaining_tables & ~real_table_bit,
6109
current_record_count,
6114
std::swap(join->best_ref[idx], *pos);
6118
'join' is either the best partial QEP with 'search_depth' relations,
6119
or the best complete QEP so far, whichever is smaller.
6121
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
6122
if (join->sort_by_table &&
6123
join->sort_by_table !=
6124
join->positions[join->const_tables].table->table)
6125
/* We have to make a temp table */
6126
current_read_time+= current_record_count;
6127
if ((search_depth == 1) || (current_read_time < join->best_read))
6129
memcpy(join->best_positions, join->positions,
6130
sizeof(POSITION) * (idx + 1));
6131
join->best_read= current_read_time - 0.001;
6134
restore_prev_nj_state(s);
6135
restore_prev_sj_state(remaining_tables, s);
6144
- TODO: this function is here only temporarily until 'greedy_search' is
6145
tested and accepted.
6152
find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count,
6155
THD *thd= join->thd;
6160
read_time+=record_count/(double) TIME_FOR_COMPARE;
6161
if (join->sort_by_table &&
6162
join->sort_by_table !=
6163
join->positions[join->const_tables].table->table)
6164
read_time+=record_count; // We have to make a temp table
6165
if (read_time < join->best_read)
6167
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
6168
join->best_read= read_time - 0.001;
6172
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
6173
return(false); /* Found better before */
6176
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
6177
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
6179
table_map real_table_bit=s->table->map;
6180
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
6181
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6183
double records, best;
6184
advance_sj_state(rest_tables, s);
6185
best_access_path(join, s, thd, rest_tables, idx, record_count,
6187
records= join->positions[idx].records_read;
6188
best= join->positions[idx].read_time;
6190
Go to the next level only if there hasn't been a better key on
6191
this level! This will cut down the search for a lot simple cases!
6193
double current_record_count=record_count*records;
6194
double current_read_time=read_time+best;
6195
if (best_record_count > current_record_count ||
6196
best_read_time > current_read_time ||
6197
(idx == join->const_tables && s->table == join->sort_by_table))
6199
if (best_record_count >= current_record_count &&
6200
best_read_time >= current_read_time &&
6201
(!(s->key_dependent & rest_tables) || records < 2.0))
6203
best_record_count=current_record_count;
6204
best_read_time=current_read_time;
6206
std::swap(join->best_ref[idx], *pos);
6207
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
6208
current_record_count,current_read_time))
6210
std::swap(join->best_ref[idx], *pos);
6212
restore_prev_nj_state(s);
6213
restore_prev_sj_state(rest_tables, s);
6214
if (join->select_options & SELECT_STRAIGHT_JOIN)
6215
break; // Don't test all combinations
6223
856
Find how much space the prevous read not const tables takes in cache.
6226
static void calc_used_field_length(THD *thd __attribute__((unused)),
858
void calc_used_field_length(Session *, JoinTable *join_tab)
6229
860
uint32_t null_fields,blobs,fields,rec_length;
6230
861
Field **f_ptr,*field;
6231
MY_BITMAP *read_set= join_tab->table->read_set;;
6233
863
null_fields= blobs= fields= rec_length=0;
6234
864
for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++)
6236
if (bitmap_is_set(read_set, field->field_index))
866
if (field->isReadSet())
6238
868
uint32_t flags=field->flags;
6240
870
rec_length+=field->pack_length();
6241
871
if (flags & BLOB_FLAG)
6243
873
if (!(flags & NOT_NULL_FLAG))
6247
877
if (null_fields)
6827
Fill in outer join related info for the execution plan structure.
6829
For each outer join operation left after simplification of the
6830
original query the function set up the following pointers in the linear
6831
structure join->join_tab representing the selected execution plan.
6832
The first inner table t0 for the operation is set to refer to the last
6833
inner table tk through the field t0->last_inner.
6834
Any inner table ti for the operation are set to refer to the first
6835
inner table ti->first_inner.
6836
The first inner table t0 for the operation is set to refer to the
6837
first inner table of the embedding outer join operation, if there is any,
6838
through the field t0->first_upper.
6839
The on expression for the outer join operation is attached to the
6840
corresponding first inner table through the field t0->on_expr_ref.
6841
Here ti are structures of the JOIN_TAB type.
6843
EXAMPLE. For the query:
6847
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
6848
ON (t1.a=t2.a AND t1.b=t3.b)
6852
given the execution plan with the table order t1,t2,t3,t4
6853
is selected, the following references will be set;
6854
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
6855
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
6856
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
6857
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
6859
@param join reference to the info fully describing the query
6862
The function assumes that the simplification procedure has been
6863
already applied to the join query (see simplify_joins).
6864
This function can be called only after the execution plan
6869
make_outerjoin_info(JOIN *join)
6871
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6873
JOIN_TAB *tab=join->join_tab+i;
6874
Table *table=tab->table;
6875
TableList *tbl= table->pos_in_table_list;
6876
TableList *embedding= tbl->embedding;
6878
if (tbl->outer_join)
6881
Table tab is the only one inner table for outer join.
6882
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
6883
is in the query above.)
6885
tab->last_inner= tab->first_inner= tab;
6886
tab->on_expr_ref= &tbl->on_expr;
6887
tab->cond_equal= tbl->cond_equal;
6889
tab->first_upper= embedding->nested_join->first_nested;
6891
for ( ; embedding ; embedding= embedding->embedding)
6893
/* Ignore sj-nests: */
6894
if (!embedding->on_expr)
6896
nested_join_st *nested_join= embedding->nested_join;
6897
if (!nested_join->counter_)
6900
Table tab is the first inner table for nested_join.
6901
Save reference to it in the nested join structure.
6903
nested_join->first_nested= tab;
6904
tab->on_expr_ref= &embedding->on_expr;
6905
tab->cond_equal= tbl->cond_equal;
6906
if (embedding->embedding)
6907
tab->first_upper= embedding->embedding->nested_join->first_nested;
6909
if (!tab->first_inner)
6910
tab->first_inner= nested_join->first_nested;
6911
if (++nested_join->counter_ < nested_join->join_list.elements)
6913
/* Table tab is the last inner table for nested join. */
6914
nested_join->first_nested->last_inner= tab;
6922
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
6924
THD *thd= join->thd;
6927
add_not_null_conds(join);
6928
table_map used_tables;
6929
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
6930
{ /* there may be a select without a cond. */
6931
if (join->tables > 1)
6932
cond->update_used_tables(); // Tablenr may have changed
6933
if (join->const_tables == join->tables &&
6934
thd->lex->current_select->master_unit() ==
6935
&thd->lex->unit) // not upper level SELECT
6936
join->const_table_map|=RAND_TABLE_BIT;
6937
{ // Check const tables
6939
make_cond_for_table(cond,
6940
join->const_table_map,
6942
for (JOIN_TAB *tab= join->join_tab+join->const_tables;
6943
tab < join->join_tab+join->tables ; tab++)
6945
if (*tab->on_expr_ref)
6947
JOIN_TAB *cond_tab= tab->first_inner;
6948
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
6949
join->const_table_map,
6953
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
6956
tmp->quick_fix_field();
6957
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
6958
new Item_cond_and(cond_tab->select_cond,
6960
if (!cond_tab->select_cond)
6962
cond_tab->select_cond->quick_fix_field();
6965
if (const_cond && !const_cond->val_int())
6967
return(1); // Impossible const condition
6971
used_tables=((select->const_tables=join->const_table_map) |
6972
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
6973
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6975
JOIN_TAB *tab=join->join_tab+i;
6977
first_inner is the X in queries like:
6978
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
6980
JOIN_TAB *first_inner_tab= tab->first_inner;
6981
table_map current_map= tab->table->map;
6982
bool use_quick_range=0;
6986
Following force including random expression in last table condition.
6987
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
6989
if (i == join->tables-1)
6990
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
6991
used_tables|=current_map;
6993
if (tab->type == JT_REF && tab->quick &&
6994
(uint) tab->ref.key == tab->quick->index &&
6995
tab->ref.key_length < tab->quick->max_used_key_length)
6997
/* Range uses longer key; Use this instead of ref on key */
7002
tab->ref.key_parts=0; // Don't use ref key.
7003
join->best_positions[i].records_read= rows2double(tab->quick->records);
7005
We will use join cache here : prevent sorting of the first
7006
table only and sort at the end.
7008
if (i != join->const_tables && join->tables > join->const_tables + 1)
7014
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
7015
if (cond && !tmp && tab->quick)
7017
if (tab->type != JT_ALL)
7020
Don't use the quick method
7021
We come here in the case where we have 'key=constant' and
7022
the test is removed by make_cond_for_table()
7030
Hack to handle the case where we only refer to a table
7031
in the ON part of an OUTER JOIN. In this case we want the code
7032
below to check if we should use 'quick' instead.
7034
tmp= new Item_int((int64_t) 1,1); // Always true
7038
if (tmp || !cond || tab->type == JT_REF || tab->type == JT_REF_OR_NULL ||
7039
tab->type == JT_EQ_REF)
7041
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
7042
thd->memdup((unsigned char*) select,
7045
return(1); // End of memory
7047
If tab is an inner table of an outer join operation,
7048
add a match guard to the pushed down predicate.
7049
The guard will turn the predicate on only after
7050
the first match for outer tables is encountered.
7055
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
7056
a cond, so neutralize the hack above.
7058
if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
7060
tab->select_cond=sel->cond=tmp;
7061
/* Push condition to storage engine if this is enabled
7062
and the condition is not guarded */
7063
tab->table->file->pushed_cond= NULL;
7064
if (thd->variables.engine_condition_pushdown)
7067
make_cond_for_table(tmp, current_map, current_map, 0);
7070
/* Push condition to handler */
7071
if (!tab->table->file->cond_push(push_cond))
7072
tab->table->file->pushed_cond= push_cond;
7077
tab->select_cond= sel->cond= NULL;
7079
sel->head=tab->table;
7082
/* Use quick key read if it's a constant and it's not used
7084
if (tab->needed_reg.is_clear_all() && tab->type != JT_EQ_REF
7085
&& (tab->type != JT_REF || (uint) tab->ref.key == tab->quick->index))
7087
sel->quick=tab->quick; // Use value from get_quick_...
7088
sel->quick_keys.clear_all();
7089
sel->needed_reg.clear_all();
7097
uint32_t ref_key=(uint) sel->head->reginfo.join_tab->ref.key+1;
7098
if (i == join->const_tables && ref_key)
7100
if (!tab->const_keys.is_clear_all() &&
7101
tab->table->reginfo.impossible_range)
7104
else if (tab->type == JT_ALL && ! use_quick_range)
7106
if (!tab->const_keys.is_clear_all() &&
7107
tab->table->reginfo.impossible_range)
7108
return(1); // Impossible range
7110
We plan to scan all rows.
7111
Check again if we should use an index.
7112
We could have used an column from a previous table in
7113
the index if we are using limit and this is the first table
7116
if ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||
7117
(!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)))
7119
/* Join with outer join condition */
7120
COND *orig_cond=sel->cond;
7121
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
7124
We can't call sel->cond->fix_fields,
7125
as it will break tab->on_expr if it's AND condition
7126
(fix_fields currently removes extra AND/OR levels).
7127
Yet attributes of the just built condition are not needed.
7128
Thus we call sel->cond->quick_fix_field for safety.
7130
if (sel->cond && !sel->cond->fixed)
7131
sel->cond->quick_fix_field();
7133
if (sel->test_quick_select(thd, tab->keys,
7134
used_tables & ~ current_map,
7135
(join->select_options &
7138
join->unit->select_limit_cnt), 0,
7142
Before reporting "Impossible WHERE" for the whole query
7143
we have to check isn't it only "impossible ON" instead
7145
sel->cond=orig_cond;
7146
if (!*tab->on_expr_ref ||
7147
sel->test_quick_select(thd, tab->keys,
7148
used_tables & ~ current_map,
7149
(join->select_options &
7152
join->unit->select_limit_cnt),0,
7154
return(1); // Impossible WHERE
7157
sel->cond=orig_cond;
7159
/* Fix for EXPLAIN */
7161
join->best_positions[i].records_read= (double)sel->quick->records;
7165
sel->needed_reg=tab->needed_reg;
7166
sel->quick_keys.clear_all();
7168
if (!sel->quick_keys.is_subset(tab->checked_keys) ||
7169
!sel->needed_reg.is_subset(tab->checked_keys))
7171
tab->keys=sel->quick_keys;
7172
tab->keys.merge(sel->needed_reg);
7173
tab->use_quick= (!sel->needed_reg.is_clear_all() &&
7174
(select->quick_keys.is_clear_all() ||
7176
(select->quick->records >= 100L)))) ?
7178
sel->read_tables= used_tables & ~current_map;
7180
if (i != join->const_tables && tab->use_quick != 2)
7181
{ /* Read with cache */
7183
(tmp=make_cond_for_table(cond,
7184
join->const_table_map |
7188
tab->cache.select=(SQL_SELECT*)
7189
thd->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
7190
tab->cache.select->cond=tmp;
7191
tab->cache.select->read_tables=join->const_table_map;
7198
Push down conditions from all on expressions.
7199
Each of these conditions are guarded by a variable
7200
that turns if off just before null complemented row for
7201
outer joins is formed. Thus, the condition from an
7202
'on expression' are guaranteed not to be checked for
7203
the null complemented row.
7206
/* First push down constant conditions from on expressions */
7207
for (JOIN_TAB *join_tab= join->join_tab+join->const_tables;
7208
join_tab < join->join_tab+join->tables ; join_tab++)
7210
if (*join_tab->on_expr_ref)
7212
JOIN_TAB *cond_tab= join_tab->first_inner;
7213
COND *tmp= make_cond_for_table(*join_tab->on_expr_ref,
7214
join->const_table_map,
7218
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
7221
tmp->quick_fix_field();
7222
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
7223
new Item_cond_and(cond_tab->select_cond,tmp);
7224
if (!cond_tab->select_cond)
7226
cond_tab->select_cond->quick_fix_field();
7230
/* Push down non-constant conditions from on expressions */
7231
JOIN_TAB *last_tab= tab;
7232
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
7235
Table tab is the last inner table of an outer join.
7236
An on expression is always attached to it.
7238
COND *on_expr= *first_inner_tab->on_expr_ref;
7240
table_map used_tables2= (join->const_table_map |
7241
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7242
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
7244
current_map= tab->table->map;
7245
used_tables2|= current_map;
7246
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
7250
JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
7252
First add the guards for match variables of
7253
all embedding outer join operations.
7255
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
7260
Now add the guard turning the predicate off for
7261
the null complemented row.
7263
tmp_cond= new Item_func_trig_cond(tmp_cond,
7267
tmp_cond->quick_fix_field();
7268
/* Add the predicate to other pushed down predicates */
7269
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
7270
new Item_cond_and(cond_tab->select_cond,
7272
if (!cond_tab->select_cond)
7274
cond_tab->select_cond->quick_fix_field();
7277
first_inner_tab= first_inner_tab->first_upper;
7286
1225
Check if given expression uses only table fields covered by the given index
9605
2754
if (!(left_const && right_const) &&
9606
2755
args[0]->result_type() == args[1]->result_type())
9610
resolve_const_item(thd, &args[1], args[0]);
9611
func->update_used_tables();
9612
change_cond_ref_to_const(thd, save_list, and_father, and_father,
9615
else if (left_const)
9617
resolve_const_item(thd, &args[0], args[1]);
9618
func->update_used_tables();
9619
change_cond_ref_to_const(thd, save_list, and_father, and_father,
9629
Simplify joins replacing outer joins by inner joins whenever it's
9632
The function, during a retrieval of join_list, eliminates those
9633
outer joins that can be converted into inner join, possibly nested.
9634
It also moves the on expressions for the converted outer joins
9635
and from inner joins to conds.
9636
The function also calculates some attributes for nested joins:
9640
- on_expr_dep_tables
9641
The first two attributes are used to test whether an outer join can
9642
be substituted for an inner join. The third attribute represents the
9643
relation 'to be dependent on' for tables. If table t2 is dependent
9644
on table t1, then in any evaluated execution plan table access to
9645
table t2 must precede access to table t2. This relation is used also
9646
to check whether the query contains invalid cross-references.
9647
The forth attribute is an auxiliary one and is used to calculate
9649
As the attribute dep_tables qualifies possibles orders of tables in the
9650
execution plan, the dependencies required by the straight join
9651
modifiers are reflected in this attribute as well.
9652
The function also removes all braces that can be removed from the join
9653
expression without changing its meaning.
9656
An outer join can be replaced by an inner join if the where condition
9657
or the on expression for an embedding nested join contains a conjunctive
9658
predicate rejecting null values for some attribute of the inner tables.
9662
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9664
the predicate t2.b < 5 rejects nulls.
9665
The query is converted first to:
9667
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9669
then to the equivalent form:
9671
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
9675
Similarly the following query:
9677
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
9682
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
9686
One conversion might trigger another:
9688
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
9689
LEFT JOIN t3 ON t3.b=t2.b
9690
WHERE t3 IS NOT NULL =>
9691
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
9692
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
9693
SELECT * FROM t1, t2, t3
9694
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
9697
The function removes all unnecessary braces from the expression
9698
produced by the conversions.
9701
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9703
finally is converted to:
9705
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9710
It also will remove braces from the following queries:
9712
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
9713
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
9716
The benefit of this simplification procedure is that it might return
9717
a query for which the optimizer can evaluate execution plan with more
9718
join orders. With a left join operation the optimizer does not
9719
consider any plan where one of the inner tables is before some of outer
9723
The function is implemented by a recursive procedure. On the recursive
9724
ascent all attributes are calculated, all outer joins that can be
9725
converted are replaced and then all unnecessary braces are removed.
9726
As join list contains join tables in the reverse order sequential
9727
elimination of outer joins does not require extra recursive calls.
9730
Remove all semi-joins that have are within another semi-join (i.e. have
9731
an "ancestor" semi-join nest)
9734
Here is an example of a join query with invalid cross references:
9736
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
9739
@param join reference to the query info
9740
@param join_list list representation of the join to be converted
9741
@param conds conditions to add on expressions for converted joins
9742
@param top true <=> conds is the where condition
9745
- The new condition, if success
9750
simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top,
9754
nested_join_st *nested_join;
9755
TableList *prev_table= 0;
9756
List_iterator<TableList> li(*join_list);
9759
Try to simplify join operations from join_list.
9760
The most outer join operation is checked for conversion first.
9762
while ((table= li++))
9764
table_map used_tables;
9765
table_map not_null_tables= (table_map) 0;
9767
if ((nested_join= table->nested_join))
9770
If the element of join_list is a nested join apply
9771
the procedure to its nested join list first.
9775
Item *expr= table->on_expr;
9777
If an on expression E is attached to the table,
9778
check all null rejected predicates in this expression.
9779
If such a predicate over an attribute belonging to
9780
an inner table of an embedded outer join is found,
9781
the outer join is converted to an inner join and
9782
the corresponding on expression is added to E.
9784
expr= simplify_joins(join, &nested_join->join_list,
9785
expr, false, in_sj || table->sj_on_expr);
9787
if (!table->prep_on_expr || expr != table->on_expr)
9791
table->on_expr= expr;
9792
table->prep_on_expr= expr->copy_andor_structure(join->thd);
9795
nested_join->used_tables= (table_map) 0;
9796
nested_join->not_null_tables=(table_map) 0;
9797
conds= simplify_joins(join, &nested_join->join_list, conds, top,
9798
in_sj || table->sj_on_expr);
9799
used_tables= nested_join->used_tables;
9800
not_null_tables= nested_join->not_null_tables;
9804
if (!table->prep_on_expr)
9805
table->prep_on_expr= table->on_expr;
9806
used_tables= table->table->map;
9808
not_null_tables= conds->not_null_tables();
9811
if (table->embedding)
9813
table->embedding->nested_join->used_tables|= used_tables;
9814
table->embedding->nested_join->not_null_tables|= not_null_tables;
9817
if (!table->outer_join || (used_tables & not_null_tables))
9820
For some of the inner tables there are conjunctive predicates
9821
that reject nulls => the outer join can be replaced by an inner join.
9823
table->outer_join= 0;
9826
/* Add ON expression to the WHERE or upper-level ON condition. */
9829
conds= and_conds(conds, table->on_expr);
9830
conds->top_level_item();
9831
/* conds is always a new item as both cond and on_expr existed */
9832
assert(!conds->fixed);
9833
conds->fix_fields(join->thd, &conds);
9836
conds= table->on_expr;
9837
table->prep_on_expr= table->on_expr= 0;
9845
Only inner tables of non-convertible outer joins
9846
remain with on_expr.
9850
table->dep_tables|= table->on_expr->used_tables();
9851
if (table->embedding)
9853
table->dep_tables&= ~table->embedding->nested_join->used_tables;
9855
Embedding table depends on tables used
9856
in embedded on expressions.
9858
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
9861
table->dep_tables&= ~table->table->map;
9866
/* The order of tables is reverse: prev_table follows table */
9867
if (prev_table->straight)
9868
prev_table->dep_tables|= used_tables;
9869
if (prev_table->on_expr)
9871
prev_table->dep_tables|= table->on_expr_dep_tables;
9872
table_map prev_used_tables= prev_table->nested_join ?
9873
prev_table->nested_join->used_tables :
9874
prev_table->table->map;
9876
If on expression contains only references to inner tables
9877
we still make the inner tables dependent on the outer tables.
9878
It would be enough to set dependency only on one outer table
9879
for them. Yet this is really a rare case.
9881
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
9882
prev_table->dep_tables|= used_tables;
9889
Flatten nested joins that can be flattened.
9890
no ON expression and not a semi-join => can be flattened.
9893
while ((table= li++))
9895
nested_join= table->nested_join;
9896
if (table->sj_on_expr && !in_sj)
9899
If this is a semi-join that is not contained within another semi-join,
9900
leave it intact (otherwise it is flattened)
9902
join->select_lex->sj_nests.push_back(table);
9904
else if (nested_join && !table->on_expr)
9907
List_iterator<TableList> it(nested_join->join_list);
9910
tbl->embedding= table->embedding;
9911
tbl->join_list= table->join_list;
9913
li.replace(nested_join->join_list);
9921
Assign each nested join structure a bit in nested_join_map.
9923
Assign each nested join structure (except "confluent" ones - those that
9924
embed only one element) a bit in nested_join_map.
9926
@param join Join being processed
9927
@param join_list List of tables
9928
@param first_unused Number of first unused bit in nested_join_map before the
9932
This function is called after simplify_joins(), when there are no
9933
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
9934
we will not run out of bits in nested_join_map.
9937
First unused bit in nested_join_map after the call.
9940
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
9941
uint32_t first_unused)
9943
List_iterator<TableList> li(*join_list);
9945
while ((table= li++))
9947
nested_join_st *nested_join;
9948
if ((nested_join= table->nested_join))
9951
It is guaranteed by simplify_joins() function that a nested join
9952
that has only one child is either
9953
- a single-table view (the child is the underlying table), or
9954
- a single-table semi-join nest
9956
We don't assign bits to such sj-nests because
9957
1. it is redundant (a "sequence" of one table cannot be interleaved
9959
2. we could run out bits in nested_join_map otherwise.
9961
if (nested_join->join_list.elements != 1)
9963
/* Don't assign bits to sj-nests */
9965
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
9966
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
9971
return(first_unused);
9976
Set nested_join_st::counter=0 in all nested joins in passed list.
9978
Recursively set nested_join_st::counter=0 for all nested joins contained in
9979
the passed join_list.
9981
@param join_list List of nested joins to process. It may also contain base
9982
tables which will be ignored.
9985
static void reset_nj_counters(List<TableList> *join_list)
9987
List_iterator<TableList> li(*join_list);
9989
while ((table= li++))
9991
nested_join_st *nested_join;
9992
if ((nested_join= table->nested_join))
9994
nested_join->counter_= 0;
9995
reset_nj_counters(&nested_join->join_list);
2759
resolve_const_item(session, &args[1], args[0]);
2760
func->update_used_tables();
2761
change_cond_ref_to_const(session, save_list, and_father, and_father,
2764
else if (left_const)
2766
resolve_const_item(session, &args[0], args[1]);
2767
func->update_used_tables();
2768
change_cond_ref_to_const(session, save_list, and_father, and_father,
10003
2777
Check interleaving with an inner tables of an outer join for
10004
2778
extension table.
10006
Check if table next_tab can be added to current partial join order, and
2780
Check if table next_tab can be added to current partial join order, and
10007
2781
if yes, record that it has been added.
10009
2783
The function assumes that both current partial join order and its
10010
2784
extension with next_tab are valid wrt table dependencies.
10014
2788
LIMITATIONS ON JOIN order_st
10015
2789
The nested [outer] joins executioner algorithm imposes these limitations
10016
2790
on join order:
10017
1. "Outer tables first" - any "outer" table must be before any
2791
1. "Outer tables first" - any "outer" table must be before any
10018
2792
corresponding "inner" table.
10019
2793
2. "No interleaving" - tables inside a nested join must form a continuous
10020
sequence in join order (i.e. the sequence must not be interrupted by
2794
sequence in join order (i.e. the sequence must not be interrupted by
10021
2795
tables that are outside of this nested join).
10023
2797
#1 is checked elsewhere, this function checks #2 provided that #1 has
10024
2798
been already checked.
10026
2800
WHY NEED NON-INTERLEAVING
10027
Consider an example:
2801
Consider an example:
10029
2803
select * from t0 join t1 left join (t2 join t3) on cond1
10909
SemiJoinDuplicateElimination: Weed out duplicate row combinations
10912
do_sj_dups_weedout()
10916
1 The row combination is a duplicate (discard it)
10917
0 The row combination is not a duplicate (continue)
10920
int do_sj_dups_weedout(THD *thd, SJ_TMP_TABLE *sjtbl)
10923
SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
10924
SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
10925
unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;
10926
unsigned char *nulls_ptr= ptr;
10928
/* Put the the rowids tuple into table->record[0]: */
10930
// 1. Store the length
10931
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
10933
*ptr= (unsigned char)(sjtbl->rowid_len + sjtbl->null_bytes);
10938
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
10942
// 2. Zero the null bytes
10943
if (sjtbl->null_bytes)
10945
memset(ptr, 0, sjtbl->null_bytes);
10946
ptr += sjtbl->null_bytes;
10949
// 3. Put the rowids
10950
for (uint32_t i=0; tab != tab_end; tab++, i++)
10952
handler *h= tab->join_tab->table->file;
10953
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
10955
/* It's a NULL-complemented row */
10956
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
10957
memset(ptr + tab->rowid_offset, 0, h->ref_length);
10961
/* Copy the rowid value */
10962
if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
10963
h->position(tab->join_tab->table->record[0]);
10964
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
10968
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
10971
/* create_myisam_from_heap will generate error if needed */
10972
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
10973
create_myisam_from_heap(thd, sjtbl->tmp_table, sjtbl->start_recinfo,
10974
&sjtbl->recinfo, error, 1))
10976
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
10984
SemiJoinDuplicateElimination: Reset the temporary table
10987
int do_sj_reset(SJ_TMP_TABLE *sj_tbl)
10989
if (sj_tbl->tmp_table)
10990
return sj_tbl->tmp_table->file->ha_delete_all_rows();
10995
Process one record of the nested loop join.
10997
This function will evaluate parts of WHERE/ON clauses that are
10998
applicable to the partial record on hand and in case of success
10999
submit this record to the next level of the nested loop.
11002
static enum_nested_loop_state
11003
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
11006
bool not_used_in_distinct=join_tab->not_used_in_distinct;
11007
ha_rows found_records=join->found_records;
11008
COND *select_cond= join_tab->select_cond;
11010
if (error > 0 || (join->thd->is_error())) // Fatal error
11011
return NESTED_LOOP_ERROR;
11013
return NESTED_LOOP_NO_MORE_ROWS;
11014
if (join->thd->killed) // Aborted by user
11016
join->thd->send_kill_message();
11017
return NESTED_LOOP_KILLED; /* purecov: inspected */
11019
if (!select_cond || select_cond->val_int())
11022
There is no select condition or the attached pushed down
11023
condition is true => a match is found.
11026
while (join_tab->first_unmatched && found)
11029
The while condition is always false if join_tab is not
11030
the last inner join table of an outer join operation.
11032
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11034
Mark that a match for current outer table is found.
11035
This activates push down conditional predicates attached
11036
to the all inner tables of the outer join.
11038
first_unmatched->found= 1;
11039
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11041
if (tab->table->reginfo.not_exists_optimize)
11042
return NESTED_LOOP_NO_MORE_ROWS;
11043
/* Check all predicates that has just been activated. */
11045
Actually all predicates non-guarded by first_unmatched->found
11046
will be re-evaluated again. It could be fixed, but, probably,
11047
it's not worth doing now.
11049
if (tab->select_cond && !tab->select_cond->val_int())
11051
/* The condition attached to table tab is false */
11052
if (tab == join_tab)
11057
Set a return point if rejected predicate is attached
11058
not to the last table of the current nest level.
11060
join->return_tab= tab;
11061
return NESTED_LOOP_OK;
11066
Check whether join_tab is not the last inner table
11067
for another embedding outer join.
11069
if ((first_unmatched= first_unmatched->first_upper) &&
11070
first_unmatched->last_inner != join_tab)
11071
first_unmatched= 0;
11072
join_tab->first_unmatched= first_unmatched;
11075
JOIN_TAB *return_tab= join->return_tab;
11076
join_tab->found_match= true;
11077
if (join_tab->check_weed_out_table)
11079
int res= do_sj_dups_weedout(join->thd, join_tab->check_weed_out_table);
11081
return NESTED_LOOP_ERROR;
11083
return NESTED_LOOP_OK;
11085
else if (join_tab->do_firstmatch)
11088
We should return to the join_tab->do_firstmatch after we have
11089
enumerated all the suffixes for current prefix row combination
11091
return_tab= join_tab->do_firstmatch;
11095
It was not just a return to lower loop level when one
11096
of the newly activated predicates is evaluated as false
11097
(See above join->return_tab= tab).
11099
join->examined_rows++;
11100
join->thd->row_count++;
11104
enum enum_nested_loop_state rc;
11105
/* A match from join_tab is found for the current partial join. */
11106
rc= (*join_tab->next_select)(join, join_tab+1, 0);
11107
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11109
if (return_tab < join->return_tab)
11110
join->return_tab= return_tab;
11112
if (join->return_tab < join_tab)
11113
return NESTED_LOOP_OK;
11115
Test if this was a SELECT DISTINCT query on a table that
11116
was not in the field list; In this case we can abort if
11117
we found a row, as no new rows can be added to the result.
11119
if (not_used_in_distinct && found_records != join->found_records)
11120
return NESTED_LOOP_NO_MORE_ROWS;
11123
join_tab->read_record.file->unlock_row();
11128
The condition pushed down to the table join_tab rejects all rows
11129
with the beginning coinciding with the current partial join.
11131
join->examined_rows++;
11132
join->thd->row_count++;
11133
join_tab->read_record.file->unlock_row();
11135
return NESTED_LOOP_OK;
11142
Construct a NULL complimented partial join record and feed it to the next
11143
level of the nested loop. This function is used in case we have
11144
an OUTER join and no matching record was found.
11147
static enum_nested_loop_state
11148
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab)
11151
The table join_tab is the first inner table of a outer join operation
11152
and no matches has been found for the current outer row.
11154
JOIN_TAB *last_inner_tab= join_tab->last_inner;
11155
/* Cache variables for faster loop */
11157
for ( ; join_tab <= last_inner_tab ; join_tab++)
11159
/* Change the the values of guard predicate variables. */
11160
join_tab->found= 1;
11161
join_tab->not_null_compl= 0;
11162
/* The outer row is complemented by nulls for each inner tables */
11163
restore_record(join_tab->table,s->default_values); // Make empty record
11164
mark_as_null_row(join_tab->table); // For group by without error
11165
select_cond= join_tab->select_cond;
11166
/* Check all attached conditions for inner table rows. */
11167
if (select_cond && !select_cond->val_int())
11168
return NESTED_LOOP_OK;
11172
The row complemented by nulls might be the first row
11173
of embedding outer joins.
11174
If so, perform the same actions as in the code
11175
for the first regular outer join row above.
11179
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11180
if ((first_unmatched= first_unmatched->first_upper) &&
11181
first_unmatched->last_inner != join_tab)
11182
first_unmatched= 0;
11183
join_tab->first_unmatched= first_unmatched;
11184
if (!first_unmatched)
11186
first_unmatched->found= 1;
11187
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11189
if (tab->select_cond && !tab->select_cond->val_int())
11191
join->return_tab= tab;
11192
return NESTED_LOOP_OK;
11197
The row complemented by nulls satisfies all conditions
11198
attached to inner tables.
11199
Send the row complemented by nulls to be joined with the
11202
return (*join_tab->next_select)(join, join_tab+1, 0);
11206
static enum_nested_loop_state
11207
flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skip_last)
11209
enum_nested_loop_state rc= NESTED_LOOP_OK;
11213
join_tab->table->null_row= 0;
11214
if (!join_tab->cache.records)
11215
return NESTED_LOOP_OK; /* Nothing to do */
11217
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
11218
if (join_tab->use_quick == 2)
11220
if (join_tab->select->quick)
11221
{ /* Used quick select last. reset it */
11222
delete join_tab->select->quick;
11223
join_tab->select->quick=0;
11226
/* read through all records */
11227
if ((error=join_init_read_record(join_tab)))
11229
reset_cache_write(&join_tab->cache);
11230
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
11233
for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
11235
tmp->status=tmp->table->status;
11236
tmp->table->status=0;
11239
info= &join_tab->read_record;
11242
if (join->thd->killed)
11244
join->thd->send_kill_message();
11245
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
11247
SQL_SELECT *select=join_tab->select;
11248
if (rc == NESTED_LOOP_OK &&
11249
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
11252
reset_cache_read(&join_tab->cache);
11253
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
11255
read_cached_record(join_tab);
11256
if (!select || !select->skip_record())
11259
if (!join_tab->check_weed_out_table ||
11260
!(res= do_sj_dups_weedout(join->thd, join_tab->check_weed_out_table)))
11262
rc= (join_tab->next_select)(join,join_tab+1,0);
11263
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11265
reset_cache_write(&join_tab->cache);
11270
return NESTED_LOOP_ERROR;
11274
} while (!(error=info->read_record(info)));
11277
read_cached_record(join_tab); // Restore current record
11278
reset_cache_write(&join_tab->cache);
11279
if (error > 0) // Fatal error
11280
return NESTED_LOOP_ERROR; /* purecov: inspected */
11281
for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
11282
tmp2->table->status=tmp2->status;
11283
return NESTED_LOOP_OK;
11286
int safe_index_read(JOIN_TAB *tab)
3595
int safe_index_read(JoinTable *tab)
11289
3598
Table *table= tab->table;