64
struct st_sargable_param;
66
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
67
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds,
68
DYNAMIC_ARRAY *keyuse);
69
static bool update_ref_and_keys(Session *session, DYNAMIC_ARRAY *keyuse,
71
uint32_t tables, COND *conds,
72
COND_EQUAL *cond_equal,
73
table_map table_map, Select_Lex *select_lex,
74
st_sargable_param **sargables);
75
62
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
76
static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);
77
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
78
table_map used_tables);
79
static bool choose_plan(JOIN *join,table_map join_tables);
81
static void best_access_path(JOIN *join, JOIN_TAB *s, Session *session,
82
table_map remaining_tables, uint32_t idx,
83
double record_count, double read_time);
84
static void optimize_straight_join(JOIN *join, table_map join_tables);
85
static bool greedy_search(JOIN *join, table_map remaining_tables,
86
uint32_t depth, uint32_t prune_level);
87
static bool best_extension_by_limited_search(JOIN *join,
88
table_map remaining_tables,
89
uint32_t idx, double record_count,
90
double read_time, uint32_t depth,
91
uint32_t prune_level);
92
static uint32_t determine_search_depth(JOIN* join);
93
extern "C" int join_tab_cmp(const void* ptr1, const void* ptr2);
94
extern "C" int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
96
TODO: 'find_best' is here only temporarily until 'greedy_search' is
99
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index,
100
double record_count,double read_time);
101
static uint32_t cache_record_length(JOIN *join,uint32_t index);
102
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
103
static bool get_best_combination(JOIN *join);
104
static store_key *get_store_key(Session *session,
105
KEYUSE *keyuse, table_map used_tables,
106
KEY_PART_INFO *key_part, unsigned char *key_buff,
107
uint32_t maybe_null);
108
static bool make_simple_join(JOIN *join,Table *tmp_table);
109
static void make_outerjoin_info(JOIN *join);
110
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
111
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
112
static bool only_eq_ref_tables(JOIN *join, order_st *order, table_map tables);
113
static void update_depend_map(JOIN *join);
114
static void update_depend_map(JOIN *join, order_st *order);
115
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond,
116
bool change_list, bool *simple_order);
117
static int return_zero_rows(JOIN *join, select_result *res,TableList *tables,
118
List<Item> &fields, bool send_row,
119
uint64_t select_options, const char *info,
121
63
static COND *build_equal_items(Session *session, COND *cond,
122
64
COND_EQUAL *inherited,
123
65
List<TableList> *join_list,
124
66
COND_EQUAL **cond_equal_ref);
125
static COND* substitute_for_best_equal_field(COND *cond,
126
COND_EQUAL *cond_equal,
127
void *table_join_idx);
128
static COND *simplify_joins(JOIN *join, List<TableList> *join_list,
129
COND *conds, bool top, bool in_sj);
130
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
131
static void restore_prev_nj_state(JOIN_TAB *last);
132
static void reset_nj_counters(List<TableList> *join_list);
133
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
134
uint32_t first_unused);
137
void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);
138
static void restore_prev_sj_state(const table_map remaining_tables,
139
const JOIN_TAB *tab);
141
static COND *optimize_cond(JOIN *join, COND *conds,
142
List<TableList> *join_list,
143
Item::cond_result *cond_value);
144
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
145
static int do_select(JOIN *join,List<Item> *fields,Table *tmp_table);
147
static enum_nested_loop_state
148
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
150
static enum_nested_loop_state
151
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
152
static enum_nested_loop_state
153
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
154
static enum_nested_loop_state
155
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
156
static enum_nested_loop_state
157
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
158
static enum_nested_loop_state
159
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
160
static enum_nested_loop_state
161
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
163
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
164
static int join_read_system(JOIN_TAB *tab);
165
static int join_read_const(JOIN_TAB *tab);
166
static int join_read_key(JOIN_TAB *tab);
167
static int join_read_always_key(JOIN_TAB *tab);
168
static int join_read_last_key(JOIN_TAB *tab);
169
static int join_no_more_records(READ_RECORD *info);
170
static int join_read_next(READ_RECORD *info);
171
static int join_read_next_different(READ_RECORD *info);
172
static int join_init_quick_read_record(JOIN_TAB *tab);
173
static int test_if_quick_select(JOIN_TAB *tab);
174
static int join_init_read_record(JOIN_TAB *tab);
175
static int join_read_first(JOIN_TAB *tab);
176
static int join_read_next_same(READ_RECORD *info);
177
static int join_read_next_same_diff(READ_RECORD *info);
178
static int join_read_last(JOIN_TAB *tab);
179
static int join_read_prev_same(READ_RECORD *info);
180
static int join_read_prev(READ_RECORD *info);
181
int join_read_always_key_or_null(JOIN_TAB *tab);
182
int join_read_next_same_or_null(READ_RECORD *info);
183
static COND *make_cond_for_table(COND *cond,table_map table,
184
table_map used_table,
185
bool exclude_expensive_cond);
186
68
static Item* part_of_refkey(Table *form,Field *field);
187
static bool test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,
188
ha_rows select_limit, bool no_changes,
190
static bool list_contains_unique_index(Table *table,
191
bool (*find_func) (Field *, void *), void *data);
192
static bool find_field_in_item_list (Field *field, void *data);
193
static bool find_field_in_order_list (Field *field, void *data);
194
static int create_sort_index(Session *session, JOIN *join, order_st *order,
195
ha_rows filesort_limit, ha_rows select_limit,
197
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields,
199
static int remove_dup_with_compare(Session *session, Table *entry, Field **field,
200
uint32_t offset, Item *having);
201
static int remove_dup_with_hash_index(Session *session,Table *table,
202
uint32_t field_count, Field **first_field,
203
uint32_t key_length, Item *having);
204
static int join_init_cache(Session *session,JOIN_TAB *tables,uint32_t table_count);
205
static uint32_t used_blob_length(CACHE_FIELD **ptr);
206
static bool store_record_in_cache(JOIN_CACHE *cache);
207
static void reset_cache_read(JOIN_CACHE *cache);
208
static void reset_cache_write(JOIN_CACHE *cache);
209
static void read_cached_record(JOIN_TAB *tab);
210
69
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
211
static order_st *create_distinct_group(Session *session, Item **ref_pointer_array,
212
order_st *order, List<Item> &fields,
213
List<Item> &all_fields,
214
bool *all_order_by_fields_used);
215
static bool test_if_subpart(order_st *a,order_st *b);
216
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
217
static void calc_group_buffer(JOIN *join,order_st *group);
218
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
219
static bool alloc_group_fields(JOIN *join,order_st *group);
220
// Create list for using with tempory table
221
static bool change_to_use_tmp_fields(Session *session, Item **ref_pointer_array,
222
List<Item> &new_list1,
223
List<Item> &new_list2,
224
uint32_t elements, List<Item> &items);
225
// Create list for using with tempory table
226
static bool change_refs_to_tmp_fields(Session *session, Item **ref_pointer_array,
227
List<Item> &new_list1,
228
List<Item> &new_list2,
229
uint32_t elements, List<Item> &items);
230
static void init_tmptable_sum_functions(Item_sum **func);
231
static void update_tmptable_sum_func(Item_sum **func,Table *tmp_table);
232
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
233
static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab);
234
static bool setup_sum_funcs(Session *session, Item_sum **func_ptr);
235
static bool init_sum_functions(Item_sum **func, Item_sum **end);
236
static bool update_sum_func(Item_sum **func);
237
void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
238
bool distinct, const char *message=NULL);
239
static Item *remove_additional_cond(Item* conds);
240
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
241
static bool test_if_ref(Item_field *left_item,Item *right_item);
242
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
243
Item *new_cond, bool fix_fields);
70
static void change_cond_ref_to_const(Session *session,
71
I_List<COND_CMP> *save_list,
76
static bool copy_blobs(Field **ptr);
245
77
static bool eval_const_cond(COND *cond)
247
79
return ((Item_func*) cond)->val_int() ? true : false;
252
83
This is used to mark equalities that were made from i-th IN-equality.
253
84
We limit semi-join InsideOut optimization to handling max 64 inequalities,
422
Function to setup clauses without sum functions.
424
inline int setup_without_group(Session *session, Item **ref_pointer_array,
428
List<Item> &all_fields,
431
order_st *group, bool *hidden_group_fields)
434
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
436
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
437
res= setup_conds(session, tables, conds);
439
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
440
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
442
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
443
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
444
group, hidden_group_fields);
445
session->lex->allow_sum_func= save_allow_sum_func;
449
256
/*****************************************************************************
450
257
Check fields, find best join, do the select and output fields.
451
258
mysql_select assumes that all tables are already opened
452
259
*****************************************************************************/
455
Prepare of whole select (including sub queries in future).
458
Add check of calculation of GROUP functions and fields:
459
SELECT COUNT(*)+table.col1 from table1;
467
JOIN::prepare(Item ***rref_pointer_array,
468
TableList *tables_init,
469
uint32_t wild_num, COND *conds_init, uint32_t og_num,
470
order_st *order_init, order_st *group_init,
472
Select_Lex *select_lex_arg,
473
Select_Lex_Unit *unit_arg)
475
// to prevent double initialization on EXPLAIN
481
group_list= group_init;
483
tables_list= tables_init;
484
select_lex= select_lex_arg;
485
select_lex->join= this;
486
join_list= &select_lex->top_join_list;
487
union_part= unit_arg->is_union();
489
session->lex->current_select->is_item_list_lookup= 1;
491
If we have already executed SELECT, then it have not sense to prevent
492
its table from update (see unique_table())
494
if (session->derived_tables_processing)
495
select_lex->exclude_from_table_unique_test= true;
497
/* Check that all tables, fields, conds and order are ok */
499
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
500
setup_tables_and_check_access(session, &select_lex->context, join_list,
501
tables_list, &select_lex->leaf_tables,
505
TableList *table_ptr;
506
for (table_ptr= select_lex->leaf_tables;
508
table_ptr= table_ptr->next_leaf)
511
if (setup_wild(session, fields_list, &all_fields, wild_num) ||
512
select_lex->setup_ref_array(session, og_num) ||
513
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
515
setup_without_group(session, (*rref_pointer_array), tables_list,
516
select_lex->leaf_tables, fields_list,
517
all_fields, &conds, order, group_list,
518
&hidden_group_fields))
519
return(-1); /* purecov: inspected */
521
ref_pointer_array= *rref_pointer_array;
525
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
526
session->where="having clause";
527
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
528
select_lex->having_fix_field= 1;
529
bool having_fix_rc= (!having->fixed &&
530
(having->fix_fields(session, &having) ||
531
having->check_cols(1)));
532
select_lex->having_fix_field= 0;
533
if (having_fix_rc || session->is_error())
534
return(-1); /* purecov: inspected */
535
session->lex->allow_sum_func= save_allow_sum_func;
539
Item_subselect *subselect;
540
Item_in_subselect *in_subs= NULL;
542
Are we in a subquery predicate?
543
TODO: the block below will be executed for every PS execution without need.
545
if ((subselect= select_lex->master_unit()->item))
547
bool do_semijoin= !test(session->variables.optimizer_switch &
548
OPTIMIZER_SWITCH_NO_SEMIJOIN);
549
if (subselect->substype() == Item_subselect::IN_SUBS)
550
in_subs= (Item_in_subselect*)subselect;
553
Check if we're in subquery that is a candidate for flattening into a
554
semi-join (which is done done in flatten_subqueries()). The
556
1. Subquery predicate is an IN/=ANY subq predicate
557
2. Subquery is a single SELECT (not a UNION)
558
3. Subquery does not have GROUP BY or order_st BY
559
4. Subquery does not use aggregate functions or HAVING
560
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
561
6. No execution method was already chosen (by a prepared statement).
563
(*). We are not in a subquery of a single table UPDATE/DELETE that
564
doesn't have a JOIN (TODO: We should handle this at some
565
point by switching to multi-table UPDATE/DELETE)
567
(**). We're not in a confluent table-less subquery, like
571
!select_lex->master_unit()->first_select()->next_select() && // 2
572
!select_lex->group_list.elements && !order && // 3
573
!having && !select_lex->with_sum_func && // 4
574
session->session_marker && // 5
575
select_lex->outer_select()->join && // (*)
576
select_lex->master_unit()->first_select()->leaf_tables && // (**)
578
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
581
if (!in_subs->left_expr->fixed &&
582
in_subs->left_expr->fix_fields(session, &in_subs->left_expr))
587
Check that the right part of the subselect contains no more than one
588
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
590
if (subselect->substype() == Item_subselect::IN_SUBS &&
591
(select_lex->item_list.elements !=
592
((Item_in_subselect*)subselect)->left_expr->cols()))
594
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
599
/* Register the subquery for further processing */
600
select_lex->outer_select()->join->sj_subselects.append(session->mem_root, in_subs);
601
in_subs->expr_join_nest= (TableList*)session->session_marker;
605
bool do_materialize= !test(session->variables.optimizer_switch &
606
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
608
Check if the subquery predicate can be executed via materialization.
609
The required conditions are:
610
1. Subquery predicate is an IN/=ANY subq predicate
611
2. Subquery is a single SELECT (not a UNION)
612
3. Subquery is not a table-less query. In this case there is no
613
point in materializing.
614
4. Subquery predicate is a top-level predicate
615
(this implies it is not negated)
616
TODO: this is a limitation that should be lifeted once we
617
implement correct NULL semantics (WL#3830)
618
5. Subquery is non-correlated
620
This is an overly restrictive condition. It can be extended to:
621
(Subquery is non-correlated ||
622
Subquery is correlated to any query outer to IN predicate ||
623
(Subquery is correlated to the immediate outer query &&
624
Subquery !contains {GROUP BY, order_st BY [LIMIT],
625
aggregate functions) && subquery predicate is not under "NOT IN"))
626
6. No execution method was already chosen (by a prepared statement).
628
(*) The subquery must be part of a SELECT statement. The current
629
condition also excludes multi-table update statements.
631
We have to determine whether we will perform subquery materialization
632
before calling the IN=>EXISTS transformation, so that we know whether to
633
perform the whole transformation or only that part of it which wraps
634
Item_in_subselect in an Item_in_optimizer.
636
if (do_materialize &&
638
!select_lex->master_unit()->first_select()->next_select() && // 2
639
select_lex->master_unit()->first_select()->leaf_tables && // 3
640
session->lex->sql_command == SQLCOM_SELECT) // *
642
if (in_subs->is_top_level_item() && // 4
643
!in_subs->is_correlated && // 5
644
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
645
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
648
Item_subselect::trans_res trans_res;
649
if ((trans_res= subselect->select_transformer(this)) !=
650
Item_subselect::RES_OK)
652
return((trans_res == Item_subselect::RES_ERROR));
661
for (ord= order; ord; ord= ord->next)
663
Item *item= *ord->item;
664
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
665
item->split_sum_func(session, ref_pointer_array, all_fields);
669
if (having && having->with_sum_func)
670
having->split_sum_func(session, ref_pointer_array, all_fields,
672
if (select_lex->inner_sum_func_list)
674
Item_sum *end=select_lex->inner_sum_func_list;
675
Item_sum *item_sum= end;
678
item_sum= item_sum->next;
679
item_sum->split_sum_func(session, ref_pointer_array,
680
all_fields, item_sum->ref_by, false);
681
} while (item_sum != end);
684
if (select_lex->inner_refs_list.elements &&
685
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
689
Check if there are references to un-aggregated columns when computing
690
aggregate functions with implicit grouping (there is no GROUP BY).
692
MODE_ONLY_FULL_GROUP_BY is enabled here by default
694
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
696
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
697
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
701
/* Caclulate the number of groups */
703
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
708
goto err; /* purecov: inspected */
710
if (result && result->prepare(fields_list, unit_arg))
711
goto err; /* purecov: inspected */
713
/* Init join struct */
714
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
715
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
716
this->group= group_list != 0;
719
#ifdef RESTRICTED_GROUP
720
if (sum_func_count && !group_list && (func_count || field_count))
722
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
726
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
728
if (alloc_func_list())
734
return(-1); /* purecov: inspected */
739
Remove the predicates pushed down into the subquery
742
JOIN::remove_subq_pushed_predicates()
743
where IN Must be NULL
744
OUT The remaining WHERE condition, or NULL
747
Given that this join will be executed using (unique|index)_subquery,
748
without "checking NULL", remove the predicates that were pushed down
751
If the subquery compares scalar values, we can remove the condition that
752
was wrapped into trig_cond (it will be checked when needed by the subquery
755
If the subquery compares row values, we need to keep the wrapped
756
equalities in the WHERE clause: when the left (outer) tuple has both NULL
757
and non-NULL values, we'll do a full table scan and will rely on the
758
equalities corresponding to non-NULL parts of left tuple to filter out
759
non-matching records.
761
TODO: We can remove the equalities that will be guaranteed to be true by the
762
fact that subquery engine will be using index lookup. This must be done only
763
for cases where there are no conversion errors of significance, e.g. 257
764
that is searched in a byte. But this requires homogenization of the return
765
codes of all Field*::store() methods.
768
void JOIN::remove_subq_pushed_predicates(Item **where)
770
if (conds->type() == Item::FUNC_ITEM &&
771
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
772
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
773
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
774
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
775
((Item_func *)conds)->arguments()[0]))
784
262
Index lookup-based subquery: save some flags for EXPLAIN output
823
Check if the table's rowid is included in the temptable
826
sj_table_is_included()
828
join_tab The table to be checked
831
SemiJoinDuplicateElimination: check the table's rowid should be included
832
in the temptable. This is so if
834
1. The table is not embedded within some semi-join nest
835
2. The has been pulled out of a semi-join nest, or
837
3. The table is functionally dependent on some previous table
839
[4. This is also true for constant tables that can't be
840
NULL-complemented but this function is not called for such tables]
843
true - Include table's rowid
847
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
849
if (join_tab->emb_sj_nest)
852
/* Check if this table is functionally dependent on the tables that
853
are within the same outer join nest
855
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
856
if (join_tab->type == JT_EQ_REF)
858
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
860
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
862
JOIN_TAB *ref_tab= join->join_tab + idx;
863
if (embedding == ref_tab->table->pos_in_table_list->embedding)
866
/* Ok, functionally dependent */
869
/* Not functionally dependent => need to include*/
875
Setup the strategies to eliminate semi-join duplicates.
878
setup_semijoin_dups_elimination()
880
options Join options (needed to see if join buffering will be
882
no_jbuf_after Another bit of information re where join buffering will
886
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
889
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
891
2. FirstMatch (pick only the 1st matching row combination of inner tables)
892
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
893
together and picking the 1st one)
895
The join order has "duplicate-generating ranges", and every range is
896
served by one strategy or a combination of FirstMatch with with some
899
"Duplicate-generating range" is defined as a range within the join order
900
that contains all of the inner tables of a semi-join. All ranges must be
901
disjoint, if tables of several semi-joins are interleaved, then the ranges
902
are joined together, which is equivalent to converting
903
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
905
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
908
Applicability conditions are as follows:
910
DuplicateWeedout strategy
911
~~~~~~~~~~~~~~~~~~~~~~~~~
913
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
914
+------+ +=========================+ +---+
917
(1) - Prefix of OuterTables (those that participate in
918
IN-equality and/or are correlated with subquery) and outer
919
Noncorrelated Tables.
920
(2) - The handled range. The range starts with the first sj-inner
921
table, and covers all sj-inner and outer tables
922
Within the range, Inner, Outer, outer Noncorrelated tables
923
may follow in any order.
924
(3) - The suffix of outer Noncorrelated tables.
929
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
930
+------+ +==================+ +---+
933
(1) - Prefix of outer and non-correlated tables
934
(2) - The handled range, which may contain only inner and
935
non-correlated tables.
936
(3) - The suffix of outer Noncorrelated tables.
941
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
942
+--------+ +===========+ +=============+ +------+
945
(1) - Prefix that may contain any outer tables. The prefix must contain
946
all the non-trivially correlated outer tables. (non-trivially means
947
that the correlation is not just through the IN-equality).
949
(2) - Inner table for which the InsideOut scan is performed.
951
(3) - The remainder of the duplicate-generating range. It is served by
952
application of FirstMatch strategy, with the exception that
953
outer IN-correlated tables are considered to be non-correlated.
955
(4) - THe suffix of outer and outer non-correlated tables.
957
If several strategies are applicable, their relative priorities are:
962
This function walks over the join order and sets up the strategies by
963
setting appropriate members in join_tab structures.
967
true Out of memory error
971
int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
973
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
976
0 - invalid (EOF marker),
978
2 - Temptable (maybe confluent),
979
3 - Temptable with join buffering
982
uint32_t start_idx; /* Left range bound */
983
uint32_t end_idx; /* Right range bound */
985
For Temptable strategy: Bitmap of all outer and correlated tables from
986
all involved join nests.
988
table_map outer_tables;
989
} dups_ranges [MAX_TABLES];
991
TableList *emb_insideout_nest= NULL;
992
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
993
tables) whose ranges we're in */
994
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
995
table_map range_start_map= 0; /* table_map at current range start */
996
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
1001
First pass: locate the duplicate-generating ranges and pick the strategies.
1003
for (i=join->const_tables ; i < join->tables ; i++)
1005
JOIN_TAB *tab=join->join_tab+i;
1006
Table *table=tab->table;
1007
cur_map |= table->map;
1009
if (tab->emb_sj_nest) // Encountered an sj-inner table
1013
dups_ranges[cur_range].start_idx= i;
1014
range_start_map= cur_map & ~table->map;
1016
Remember if this is a possible start of range that is covered by
1017
the InsideOut strategy (the reason that it is not covered could
1018
be that it overlaps with anther semi-join's range. we don't
1019
support InsideOut for joined ranges)
1021
if (join->best_positions[i].use_insideout_scan)
1022
emb_insideout_nest= tab->emb_sj_nest;
1025
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
1026
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
1028
if (tab->emb_sj_nest != emb_insideout_nest)
1031
Two different semi-joins interleave. This cannot be handled by
1034
emb_insideout_nest= NULL;
1038
if (emb_sj_map) /* We're in duplicate-generating range */
1040
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
1041
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
1042
i <= no_jbuf_after && !dealing_with_jbuf)
1045
This table uses join buffering, which makes use of FirstMatch or
1046
InsideOut strategies impossible for the current and (we assume)
1047
preceding duplicate-producing ranges.
1048
That is, for the join order:
1050
x x [ x x] x [x x x] x [x x X* x] x
1052
+-----+ +-----+ | join buffering use
1055
we'll have to remove r1 and r2 and use duplicate-elimination
1056
strategy that spans all the tables, starting from the very 1st
1059
dealing_with_jbuf= true;
1060
emb_insideout_nest= false;
1063
Absorb all preceding duplicate-eliminating ranges. Their strategies
1066
for (int prev_range= 0; prev_range < cur_range; prev_range++)
1068
dups_ranges[cur_range].outer_tables |=
1069
dups_ranges[prev_range].outer_tables;
1071
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
1072
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
1077
Check if we are at the end of duplicate-producing range. We are if
1079
1. It's an InsideOut range (which presumes all correlated tables are
1080
in the prefix), and all inner tables are in the join order prefix,
1082
2. It's a DuplicateElimination range (possibly covering several
1083
SJ-nests), and all inner, outer, and correlated tables of all
1084
sj-nests are in the join order prefix.
1086
bool end_of_range= false;
1087
if (emb_insideout_nest &&
1088
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
1090
/* Save that this range is handled with InsideOut: */
1091
dups_ranges[cur_range].strategy= 1;
1094
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
1097
This is a complete range to be handled with either DuplicateWeedout
1100
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
1102
This will hold tables from within the range that need to be put
1103
into the join buffer before we can use the FirstMatch on its tail.
1105
dups_ranges[cur_range].outer_tables= emb_outer_tables &
1112
dups_ranges[cur_range].end_idx= i+1;
1113
emb_sj_map= emb_outer_tables= 0;
1114
emb_insideout_nest= NULL;
1115
dealing_with_jbuf= false;
1116
dups_ranges[++cur_range].strategy= 0;
1121
Session *session= join->session;
1122
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
1124
Second pass: setup the chosen strategies
1126
for (int j= 0; j < cur_range; j++)
1128
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
1130
if (dups_ranges[j].strategy == 1) // InsideOut strategy
1132
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
1135
else // DuplicateWeedout strategy
1137
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
1138
table_map weed_cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
1139
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
1140
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
1141
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
1142
uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
1143
JOIN_TAB *last_outer_tab= tab - 1;
1145
Walk through the range and remember
1146
- tables that need their rowids to be put into temptable
1147
- the last outer table
1149
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1151
if (sj_table_is_included(join, tab))
1153
last_tab->join_tab= tab;
1154
last_tab->rowid_offset= jt_rowid_offset;
1155
jt_rowid_offset += tab->table->file->ref_length;
1156
if (tab->table->maybe_null)
1158
last_tab->null_byte= jt_null_bits / 8;
1159
last_tab->null_bit= jt_null_bits++;
1162
tab->table->prepare_for_position();
1163
tab->rowid_keep_flags= rowid_keep_flags;
1165
weed_cur_map |= tab->table->map;
1166
if (!tab->emb_sj_nest && bitmap_covers(weed_cur_map,
1167
dups_ranges[j].outer_tables))
1168
last_outer_tab= tab;
1171
if (jt_rowid_offset) /* Temptable has at least one rowid */
1173
SJ_TMP_TABLE *sjtbl;
1174
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
1175
if (!(sjtbl= (SJ_TMP_TABLE*)session->alloc(sizeof(SJ_TMP_TABLE))) ||
1176
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) session->alloc(tabs_size)))
1178
memcpy(sjtbl->tabs, sjtabs, tabs_size);
1179
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
1180
sjtbl->rowid_len= jt_rowid_offset;
1181
sjtbl->null_bits= jt_null_bits;
1182
sjtbl->null_bytes= (jt_null_bits + 7)/8;
1184
*next_sjtbl_ptr= sjtbl;
1185
next_sjtbl_ptr= &(sjtbl->next);
1189
create_duplicate_weedout_tmp_table(session,
1194
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
1195
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
1197
tab= last_outer_tab + 1;
1198
jump_to= last_outer_tab;
1201
/* Create the FirstMatch tail */
1202
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1204
if (tab->emb_sj_nest)
1205
tab->do_firstmatch= jump_to;
1214
static void cleanup_sj_tmp_tables(JOIN *join)
1216
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
1217
sj_tbl= sj_tbl->next)
1219
if (sj_tbl->tmp_table)
1221
sj_tbl->tmp_table->free_tmp_table(join->session);
1224
join->sj_tmp_tables= NULL;
1227
uint32_t make_join_orderinfo(JOIN *join);
1230
global select optimisation.
1233
error code saved in field 'error'
1244
// to prevent double initialization on EXPLAIN
1249
session->set_proc_info("optimizing");
1250
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
1251
unit->select_limit_cnt);
1252
/* select_limit is used to decide if we are likely to scan the whole table */
1253
select_limit= unit->select_limit_cnt;
1254
if (having || (select_options & OPTION_FOUND_ROWS))
1255
select_limit= HA_POS_ERROR;
1256
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
1257
// Ignore errors of execution if option IGNORE present
1258
if (session->lex->ignore)
1259
session->lex->current_select->no_error= 1;
1261
#ifdef HAVE_REF_TO_FIELDS // Not done yet
1262
/* Add HAVING to WHERE if possible */
1263
if (having && !group_list && !sum_func_count)
1270
else if ((conds=new Item_cond_and(conds,having)))
1273
Item_cond_and can't be fixed after creation, so we do not check
1276
conds->fix_fields(session, &conds);
1277
conds->change_ref_to_fields(session, tables_list);
1278
conds->top_level_item();
1284
/* Convert all outer joins to inner joins if possible */
1285
conds= simplify_joins(this, join_list, conds, true, false);
1286
build_bitmap_for_nested_joins(join_list, 0);
1288
conds= optimize_cond(this, conds, join_list, &cond_value);
1289
if (session->is_error())
1296
having= optimize_cond(this, having, join_list, &having_value);
1297
if (session->is_error())
1302
if (select_lex->where)
1303
select_lex->cond_value= cond_value;
1304
if (select_lex->having)
1305
select_lex->having_value= having_value;
1307
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
1308
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
1309
{ /* Impossible cond */
1310
zero_result_cause= having_value == Item::COND_FALSE ?
1311
"Impossible HAVING" : "Impossible WHERE";
1317
/* Optimize count(*), cmin() and cmax() */
1318
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
1322
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
1323
to the WHERE conditions,
1324
or 1 if all items were resolved,
1325
or 0, or an error number HA_ERR_...
1327
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
1329
if (res == HA_ERR_KEY_NOT_FOUND)
1331
zero_result_cause= "No matching min/max row";
1342
zero_result_cause= "No matching min/max row";
1346
zero_result_cause= "Select tables optimized away";
1347
tables_list= 0; // All tables resolved
1349
Extract all table-independent conditions and replace the WHERE
1350
clause with them. All other conditions were computed by opt_sum_query
1351
and the MIN/MAX/COUNT function(s) have been replaced by constants,
1352
so there is no need to compute the whole WHERE clause again.
1353
Notice that make_cond_for_table() will always succeed to remove all
1354
computed conditions, because opt_sum_query() is applicable only to
1356
Preserve conditions for EXPLAIN.
1358
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
1360
COND *table_independent_conds=
1361
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
1362
conds= table_independent_conds;
1371
error= -1; // Error is sent to client
1372
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
1374
/* Calculate how to do the join */
1375
session->set_proc_info("statistics");
1376
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
1377
session->is_fatal_error)
1382
/* Remove distinct if only const tables */
1383
select_distinct= select_distinct && (const_tables != tables);
1384
session->set_proc_info("preparing");
1385
if (result->initialize_tables(this))
1387
return(1); // error == -1
1389
if (const_table_map != found_const_table_map &&
1390
!(select_options & SELECT_DESCRIBE) &&
1392
!(conds->used_tables() & RAND_TABLE_BIT) ||
1393
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
1395
zero_result_cause= "no matching row in const table";
1399
if (!(session->options & OPTION_BIG_SELECTS) &&
1400
best_read > (double) session->variables.max_join_size &&
1401
!(select_options & SELECT_DESCRIBE))
1402
{ /* purecov: inspected */
1403
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
1407
if (const_tables && !session->locked_tables &&
1408
!(select_options & SELECT_NO_UNLOCK))
1409
mysql_unlock_some_tables(session, table, const_tables);
1410
if (!conds && outer_join)
1412
/* Handle the case where we have an OUTER JOIN without a WHERE */
1413
conds=new Item_int((int64_t) 1,1); // Always true
1415
select= make_select(*table, const_table_map,
1416
const_table_map, conds, 1, &error);
1418
{ /* purecov: inspected */
1419
error= -1; /* purecov: inspected */
1423
reset_nj_counters(join_list);
1424
make_outerjoin_info(this);
1427
Among the equal fields belonging to the same multiple equality
1428
choose the one that is to be retrieved first and substitute
1429
all references to these in where condition for a reference for
1434
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
1435
conds->update_used_tables();
1439
Permorm the the optimization on fields evaluation mentioned above
1440
for all on expressions.
1442
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
1444
if (*tab->on_expr_ref)
1446
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
1449
(*tab->on_expr_ref)->update_used_tables();
1453
if (conds &&!outer_join && const_table_map != found_const_table_map &&
1454
(select_options & SELECT_DESCRIBE) &&
1455
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
1457
conds=new Item_int((int64_t) 0,1); // Always false
1459
if (make_join_select(this, select, conds))
1462
"Impossible WHERE noticed after reading const tables";
1463
return(0); // error == 0
1466
error= -1; /* if goto err */
1468
/* Optimize distinct away if possible */
1470
order_st *org_order= order;
1471
order=remove_constants(this, order,conds,1, &simple_order);
1472
if (session->is_error())
1479
If we are using order_st BY NULL or order_st BY const_expression,
1480
return result in any order (even if we are using a GROUP BY)
1482
if (!order && org_order)
1486
Check if we can optimize away GROUP BY/DISTINCT.
1487
We can do that if there are no aggregate functions, the
1488
fields in DISTINCT clause (if present) and/or columns in GROUP BY
1489
(if present) contain direct references to all key parts of
1490
an unique index (in whatever order) and if the key parts of the
1491
unique index cannot contain NULLs.
1492
Note that the unique keys for DISTINCT and GROUP BY should not
1493
be the same (as long as they are unique).
1495
The FROM clause must contain a single non-constant table.
1497
if (tables - const_tables == 1 && (group_list || select_distinct) &&
1498
!tmp_table_param.sum_func_count &&
1499
(!join_tab[const_tables].select ||
1500
!join_tab[const_tables].select->quick ||
1501
join_tab[const_tables].select->quick->get_type() !=
1502
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
1505
list_contains_unique_index(join_tab[const_tables].table,
1506
find_field_in_order_list,
1507
(void *) group_list))
1510
We have found that grouping can be removed since groups correspond to
1511
only one row anyway, but we still have to guarantee correct result
1512
order. The line below effectively rewrites the query from GROUP BY
1513
<fields> to order_st BY <fields>. There are two exceptions:
1514
- if skip_sort_order is set (see above), then we can simply skip
1516
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
1517
with the GROUP BY ones, i.e. either one is a prefix of another.
1518
We only check if the order_st BY is a prefix of GROUP BY. In this case
1519
test_if_subpart() copies the ASC/DESC attributes from the original
1521
If GROUP BY is a prefix of order_st BY, then it is safe to leave
1524
if (!order || test_if_subpart(group_list, order))
1525
order= skip_sort_order ? 0 : group_list;
1527
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
1528
rewritten to IGNORE INDEX FOR order_st BY(fields).
1530
join_tab->table->keys_in_use_for_order_by=
1531
join_tab->table->keys_in_use_for_group_by;
1535
if (select_distinct &&
1536
list_contains_unique_index(join_tab[const_tables].table,
1537
find_field_in_item_list,
1538
(void *) &fields_list))
1543
if (group_list || tmp_table_param.sum_func_count)
1545
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
1548
else if (select_distinct && tables - const_tables == 1)
1551
We are only using one table. In this case we change DISTINCT to a
1553
- The GROUP BY can be done through indexes (no sort) and the order_st
1554
BY only uses selected fields.
1555
(In this case we can later optimize away GROUP BY and order_st BY)
1556
- We are scanning the whole table without LIMIT
1558
- We are using CALC_FOUND_ROWS
1559
- We are using an order_st BY that can't be optimized away.
1561
We don't want to use this optimization when we are using LIMIT
1562
because in this case we can just create a temporary table that
1563
holds LIMIT rows and stop when this table is full.
1565
JOIN_TAB *tab= &join_tab[const_tables];
1566
bool all_order_fields_used;
1568
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
1569
&tab->table->keys_in_use_for_order_by);
1570
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
1571
order, fields_list, all_fields,
1572
&all_order_fields_used)))
1574
bool skip_group= (skip_sort_order &&
1575
test_if_skip_sort_order(tab, group_list, select_limit, 1,
1576
&tab->table->keys_in_use_for_group_by) != 0);
1577
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
1578
if ((skip_group && all_order_fields_used) ||
1579
select_limit == HA_POS_ERROR ||
1580
(order && !skip_sort_order))
1582
/* Change DISTINCT to GROUP BY */
1585
if (all_order_fields_used)
1587
if (order && skip_sort_order)
1590
Force MySQL to read the table in sorted order to get result in
1593
tmp_table_param.quick_group=0;
1597
group=1; // For end_write_group
1602
else if (session->is_fatal_error) // End of memory
1607
order_st *old_group_list;
1608
group_list= remove_constants(this, (old_group_list= group_list), conds,
1609
rollup.state == ROLLUP::STATE_NONE,
1611
if (session->is_error())
1616
if (old_group_list && !group_list)
1619
if (!group_list && group)
1621
order=0; // The output has only one row
1623
select_distinct= 0; // No need in distinct for 1 row
1624
group_optimized_away= 1;
1627
calc_group_buffer(this, group_list);
1628
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
1630
if (test_if_subpart(group_list, order) ||
1631
(!group_list && tmp_table_param.sum_func_count))
1634
// Can't use sort on head table if using row cache
1644
Check if we need to create a temporary table.
1645
This has to be done if all tables are not already read (const tables)
1646
and one of the following conditions holds:
1647
- We are using DISTINCT (simple distinct's are already optimized away)
1648
- We are using an order_st BY or GROUP BY on fields not in the first table
1649
- We are using different order_st BY and GROUP BY orders
1650
- The user wants us to buffer the result.
1652
need_tmp= (const_tables != tables &&
1653
((select_distinct || !simple_order || !simple_group) ||
1654
(group_list && order) ||
1655
test(select_options & OPTION_BUFFER_RESULT)));
1657
uint32_t no_jbuf_after= make_join_orderinfo(this);
1658
uint64_t select_opts_for_readinfo=
1659
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
1661
sj_tmp_tables= NULL;
1662
if (!select_lex->sj_nests.is_empty())
1663
setup_semijoin_dups_elimination(this, select_opts_for_readinfo,
1666
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1667
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1670
/* Create all structures needed for materialized subquery execution. */
1671
if (setup_subquery_materialization())
1675
is this simple IN subquery?
1677
if (!group_list && !order &&
1678
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1679
tables == 1 && conds &&
1685
if (join_tab[0].type == JT_EQ_REF &&
1686
join_tab[0].ref.items[0]->name == in_left_expr_name)
1688
remove_subq_pushed_predicates(&where);
1689
save_index_subquery_explain_info(join_tab, where);
1690
join_tab[0].type= JT_UNIQUE_SUBQUERY;
1694
subselect_uniquesubquery_engine(session,
1699
else if (join_tab[0].type == JT_REF &&
1700
join_tab[0].ref.items[0]->name == in_left_expr_name)
1702
remove_subq_pushed_predicates(&where);
1703
save_index_subquery_explain_info(join_tab, where);
1704
join_tab[0].type= JT_INDEX_SUBQUERY;
1708
subselect_indexsubquery_engine(session,
1715
} else if (join_tab[0].type == JT_REF_OR_NULL &&
1716
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1717
having->name == in_having_cond)
1719
join_tab[0].type= JT_INDEX_SUBQUERY;
1721
conds= remove_additional_cond(conds);
1722
save_index_subquery_explain_info(join_tab, conds);
1724
change_engine(new subselect_indexsubquery_engine(session,
1734
Need to tell handlers that to play it safe, it should fetch all
1735
columns of the primary key of the tables: this is because MySQL may
1736
build row pointers for the rows, and for all columns of the primary key
1737
the read set has not necessarily been set by the server code.
1739
if (need_tmp || select_distinct || group_list || order)
1741
for (uint32_t i = const_tables; i < tables; i++)
1742
join_tab[i].table->prepare_for_position();
1745
if (const_tables != tables)
1748
Because filesort always does a full table scan or a quick range scan
1749
we must add the removed reference to the select for the table.
1750
We only need to do this when we have a simple_order or simple_group
1751
as in other cases the join is done before the sort.
1753
if ((order || group_list) &&
1754
(join_tab[const_tables].type != JT_ALL) &&
1755
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
1756
((order && simple_order) || (group_list && simple_group)))
1758
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
1763
if (!(select_options & SELECT_BIG_RESULT) &&
1766
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1767
unit->select_limit_cnt, 0,
1768
&join_tab[const_tables].table->
1769
keys_in_use_for_group_by))) ||
1771
tmp_table_param.quick_group)
1773
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1778
Force using of tmp table if sorting by a SP or UDF function due to
1779
their expensive and probably non-deterministic nature.
1781
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1783
Item *item= *tmp_order->item;
1784
if (item->is_expensive())
1786
/* Force tmp table without sort */
1787
need_tmp=1; simple_order=simple_group=0;
1795
if (select_options & SELECT_DESCRIBE)
1803
The loose index scan access method guarantees that all grouping or
1804
duplicate row elimination (for distinct) is already performed
1805
during data retrieval, and that all MIN/MAX functions are already
1806
computed for each group. Thus all MIN/MAX functions should be
1807
treated as regular functions, and there is no need to perform
1808
grouping in the main execution loop.
1809
Notice that currently loose index scan is applicable only for
1810
single table queries, thus it is sufficient to test only the first
1811
join_tab element of the plan for its access method.
1813
if (join_tab->is_using_loose_index_scan())
1814
tmp_table_param.precomputed_group_by= true;
1816
/* Create a tmp table if distinct or if the sort is too complicated */
1819
session->set_proc_info("Creating tmp table");
1821
init_items_ref_array();
1823
tmp_table_param.hidden_field_count= (all_fields.elements -
1824
fields_list.elements);
1825
order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1828
Pushing LIMIT to the temporary table creation is not applicable
1829
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1830
there are aggregate functions, because in all these cases we need
1833
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1835
!session->lex->current_select->with_sum_func) ?
1836
select_limit : HA_POS_ERROR;
1838
if (!(exec_tmp_table1=
1839
create_tmp_table(session, &tmp_table_param, all_fields,
1841
group_list ? 0 : select_distinct,
1842
group_list && simple_group,
1851
We don't have to store rows in temp table that doesn't match HAVING if:
1852
- we are sorting the table and writing complete group rows to the
1854
- We are using DISTINCT without resolving the distinct as a GROUP BY
1857
If having is not handled here, it will be checked before the row
1858
is sent to the client.
1861
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1864
/* if group or order on first table, sort first */
1865
if (group_list && simple_group)
1867
session->set_proc_info("Sorting for group");
1868
if (create_sort_index(session, this, group_list,
1869
HA_POS_ERROR, HA_POS_ERROR, false) ||
1870
alloc_group_fields(this, group_list) ||
1871
make_sum_func_list(all_fields, fields_list, 1) ||
1872
setup_sum_funcs(session, sum_funcs))
1880
if (make_sum_func_list(all_fields, fields_list, 0) ||
1881
setup_sum_funcs(session, sum_funcs))
1886
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1888
session->set_proc_info("Sorting for order");
1889
if (create_sort_index(session, this, order,
1890
HA_POS_ERROR, HA_POS_ERROR, true))
1899
Optimize distinct when used on some of the tables
1900
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1901
In this case we can stop scanning t2 when we have found one t1.a
1904
if (exec_tmp_table1->distinct)
1906
table_map used_tables= session->used_tables;
1907
JOIN_TAB *last_join_tab= join_tab+tables-1;
1910
if (used_tables & last_join_tab->table->map)
1912
last_join_tab->not_used_in_distinct=1;
1913
} while (last_join_tab-- != join_tab);
1914
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1915
if (order && skip_sort_order)
1917
/* Should always succeed */
1918
if (test_if_skip_sort_order(&join_tab[const_tables],
1919
order, unit->select_limit_cnt, 0,
1920
&join_tab[const_tables].table->
1921
keys_in_use_for_order_by))
1927
If this join belongs to an uncacheable subquery save
1930
if (select_lex->uncacheable && !is_top_level_join() &&
1931
init_save_join_tab())
1932
return(-1); /* purecov: inspected */
1941
Restore values in temporary join.
1943
void JOIN::restore_tmp()
1945
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1951
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1952
select_lex->offset_limit->val_uint() :
1957
if (exec_tmp_table1)
1959
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1960
exec_tmp_table1->file->ha_delete_all_rows();
1961
free_io_cache(exec_tmp_table1);
1962
filesort_free_buffers(exec_tmp_table1,0);
1964
if (exec_tmp_table2)
1966
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1967
exec_tmp_table2->file->ha_delete_all_rows();
1968
free_io_cache(exec_tmp_table2);
1969
filesort_free_buffers(exec_tmp_table2,0);
1972
set_items_ref_array(items0);
1975
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1980
/* Reset of sum functions */
1983
Item_sum *func, **func_ptr= sum_funcs;
1984
while ((func= *(func_ptr++)))
1992
@brief Save the original join layout
1994
@details Saves the original join layout so it can be reused in
1995
re-execution and for EXPLAIN.
1997
@return Operation status
1999
@retval 1 error occurred.
2003
JOIN::init_save_join_tab()
2005
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
2006
return 1; /* purecov: inspected */
2007
error= 0; // Ensure that tmp_join.error= 0
2014
JOIN::save_join_tab()
2016
if (!join_tab_save && select_lex->master_unit()->uncacheable)
2018
if (!(join_tab_save= (JOIN_TAB*)session->memdup((unsigned char*) join_tab,
2019
sizeof(JOIN_TAB) * tables)))
2030
Note, that create_sort_index calls test_if_skip_sort_order and may
2031
finally replace sorting with index scan if there is a LIMIT clause in
2032
the query. It's never shown in EXPLAIN!
2035
When can we have here session->net.report_error not zero?
2039
List<Item> *columns_list= &fields_list;
2042
session->set_proc_info("executing");
2045
if (!tables_list && (tables || !select_lex->with_sum_func))
2047
/* Only test of functions */
2048
if (select_options & SELECT_DESCRIBE)
2049
select_describe(this, false, false, false, (zero_result_cause?zero_result_cause:"No tables used"));
2052
result->send_fields(*columns_list, Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2054
We have to test for 'conds' here as the WHERE may not be constant
2055
even if we don't have any tables for prepared statements or if
2056
conds uses something like 'rand()'.
2058
if (cond_value != Item::COND_FALSE &&
2059
(!conds || conds->val_int()) &&
2060
(!having || having->val_int()))
2062
if (do_send_rows && result->send_data(fields_list))
2066
error= (int) result->send_eof();
2067
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
2072
error= (int) result->send_eof();
2076
/* Single select (without union) always returns 0 or 1 row */
2077
session->limit_found_rows= send_records;
2078
session->examined_row_count= 0;
2082
Don't reset the found rows count if there're no tables as
2083
FOUND_ROWS() may be called. Never reset the examined row count here.
2084
It must be accumulated from all join iterations of all join parts.
2087
session->limit_found_rows= 0;
2089
if (zero_result_cause)
2091
(void) return_zero_rows(this, result, select_lex->leaf_tables,
2093
send_row_on_empty_set(),
2100
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) && get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
2103
if (select_options & SELECT_DESCRIBE)
2106
Check if we managed to optimize order_st BY away and don't use temporary
2107
table to resolve order_st BY: in that case, we only may need to do
2108
filesort for GROUP BY.
2110
if (!order && !no_order && (!skip_sort_order || !need_tmp))
2112
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
2114
simple_order= simple_group;
2117
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
2119
if (const_tables == tables
2120
|| ((simple_order || skip_sort_order)
2121
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
2125
select_describe(this, need_tmp, order != 0 && !skip_sort_order, select_distinct, !tables ? "No tables used" : NULL);
2129
JOIN *curr_join= this;
2130
List<Item> *curr_all_fields= &all_fields;
2131
List<Item> *curr_fields_list= &fields_list;
2132
Table *curr_tmp_table= 0;
2134
Initialize examined rows here because the values from all join parts
2135
must be accumulated in examined_row_count. Hence every join
2136
iteration must count from zero.
2138
curr_join->examined_rows= 0;
2140
/* Create a tmp table if distinct or if the sort is too complicated */
2146
We are in a non cacheable sub query. Get the saved join structure
2148
(curr_join may have been modified during last exection and we need
2151
curr_join= tmp_join;
2153
curr_tmp_table= exec_tmp_table1;
2155
/* Copy data to the temporary table */
2156
session->set_proc_info("Copying to tmp table");
2157
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
2158
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2159
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2164
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
2166
if (curr_join->having)
2167
curr_join->having= curr_join->tmp_having= 0; // Allready done
2169
/* Change sum_fields reference to calculated fields in tmp_table */
2170
curr_join->all_fields= *curr_all_fields;
2173
items1= items0 + all_fields.elements;
2174
if (sort_and_group || curr_tmp_table->group)
2176
if (change_to_use_tmp_fields(session, items1,
2177
tmp_fields_list1, tmp_all_fields1,
2178
fields_list.elements, all_fields))
2183
if (change_refs_to_tmp_fields(session, items1,
2184
tmp_fields_list1, tmp_all_fields1,
2185
fields_list.elements, all_fields))
2188
curr_join->tmp_all_fields1= tmp_all_fields1;
2189
curr_join->tmp_fields_list1= tmp_fields_list1;
2190
curr_join->items1= items1;
2192
curr_all_fields= &tmp_all_fields1;
2193
curr_fields_list= &tmp_fields_list1;
2194
curr_join->set_items_ref_array(items1);
2196
if (sort_and_group || curr_tmp_table->group)
2198
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
2199
+ curr_join->tmp_table_param.func_count;
2200
curr_join->tmp_table_param.sum_func_count= 0;
2201
curr_join->tmp_table_param.func_count= 0;
2205
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
2206
curr_join->tmp_table_param.func_count= 0;
2209
if (curr_tmp_table->group)
2210
{ // Already grouped
2211
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
2212
curr_join->order= curr_join->group_list; /* order by group */
2213
curr_join->group_list= 0;
2217
If we have different sort & group then we must sort the data by group
2218
and copy it to another tmp table
2219
This code is also used if we are using distinct something
2220
we haven't been able to store in the temporary table yet
2221
like SEC_TO_TIME(SUM(...)).
2224
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
2225
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
2226
{ /* Must copy to another table */
2227
/* Free first data from old join */
2228
curr_join->join_free();
2229
if (make_simple_join(curr_join, curr_tmp_table))
2231
calc_group_buffer(curr_join, group_list);
2232
count_field_types(select_lex, &curr_join->tmp_table_param,
2233
curr_join->tmp_all_fields1,
2234
curr_join->select_distinct && !curr_join->group_list);
2235
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
2236
- curr_join->tmp_fields_list1.elements;
2238
if (exec_tmp_table2)
2239
curr_tmp_table= exec_tmp_table2;
2242
/* group data to new table */
2245
If the access method is loose index scan then all MIN/MAX
2246
functions are precomputed, and should be treated as regular
2247
functions. See extended comment in JOIN::exec.
2249
if (curr_join->join_tab->is_using_loose_index_scan())
2250
curr_join->tmp_table_param.precomputed_group_by= true;
2252
if (!(curr_tmp_table=
2253
exec_tmp_table2= create_tmp_table(session,
2254
&curr_join->tmp_table_param,
2257
curr_join->select_distinct &&
2258
!curr_join->group_list,
2259
1, curr_join->select_options,
2263
curr_join->exec_tmp_table2= exec_tmp_table2;
2265
if (curr_join->group_list)
2267
session->set_proc_info("Creating sort index");
2268
if (curr_join->join_tab == join_tab && save_join_tab())
2272
if (create_sort_index(session, curr_join, curr_join->group_list,
2273
HA_POS_ERROR, HA_POS_ERROR, false) ||
2274
make_group_fields(this, curr_join))
2278
sortorder= curr_join->sortorder;
2281
session->set_proc_info("Copying to group table");
2283
if (curr_join != this)
2287
curr_join->sum_funcs= sum_funcs2;
2288
curr_join->sum_funcs_end= sum_funcs_end2;
2292
curr_join->alloc_func_list();
2293
sum_funcs2= curr_join->sum_funcs;
2294
sum_funcs_end2= curr_join->sum_funcs_end;
2297
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
2299
curr_join->group_list= 0;
2301
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
2302
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2304
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
2305
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2310
end_read_record(&curr_join->join_tab->read_record);
2311
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
2312
curr_join->join_tab[0].table= 0; // Table is freed
2314
// No sum funcs anymore
2317
items2= items1 + all_fields.elements;
2318
if (change_to_use_tmp_fields(session, items2,
2319
tmp_fields_list2, tmp_all_fields2,
2320
fields_list.elements, tmp_all_fields1))
2322
curr_join->tmp_fields_list2= tmp_fields_list2;
2323
curr_join->tmp_all_fields2= tmp_all_fields2;
2325
curr_fields_list= &curr_join->tmp_fields_list2;
2326
curr_all_fields= &curr_join->tmp_all_fields2;
2327
curr_join->set_items_ref_array(items2);
2328
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
2329
curr_join->tmp_table_param.sum_func_count= 0;
2331
if (curr_tmp_table->distinct)
2332
curr_join->select_distinct=0; /* Each row is unique */
2334
curr_join->join_free(); /* Free quick selects */
2335
if (curr_join->select_distinct && ! curr_join->group_list)
2337
session->set_proc_info("Removing duplicates");
2338
if (curr_join->tmp_having)
2339
curr_join->tmp_having->update_used_tables();
2341
if (remove_duplicates(curr_join, curr_tmp_table,
2342
*curr_fields_list, curr_join->tmp_having))
2345
curr_join->tmp_having=0;
2346
curr_join->select_distinct=0;
2348
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
2349
if (make_simple_join(curr_join, curr_tmp_table))
2351
calc_group_buffer(curr_join, curr_join->group_list);
2352
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
2356
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
2358
if (make_group_fields(this, curr_join))
2364
init_items_ref_array();
2365
items3= ref_pointer_array + (all_fields.elements*4);
2366
setup_copy_fields(session, &curr_join->tmp_table_param,
2367
items3, tmp_fields_list3, tmp_all_fields3,
2368
curr_fields_list->elements, *curr_all_fields);
2369
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
2370
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
2371
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
2372
curr_join->tmp_all_fields3= tmp_all_fields3;
2373
curr_join->tmp_fields_list3= tmp_fields_list3;
2377
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
2378
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
2379
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
2381
curr_fields_list= &tmp_fields_list3;
2382
curr_all_fields= &tmp_all_fields3;
2383
curr_join->set_items_ref_array(items3);
2385
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2387
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2388
session->is_fatal_error)
2391
if (curr_join->group_list || curr_join->order)
2393
session->set_proc_info("Sorting result");
2394
/* If we have already done the group, add HAVING to sorted table */
2395
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
2397
// Some tables may have been const
2398
curr_join->tmp_having->update_used_tables();
2399
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
2400
table_map used_tables= (curr_join->const_table_map |
2401
curr_table->table->map);
2403
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
2404
if (sort_table_cond)
2406
if (!curr_table->select)
2407
if (!(curr_table->select= new SQL_SELECT))
2409
if (!curr_table->select->cond)
2410
curr_table->select->cond= sort_table_cond;
2411
else // This should never happen
2413
if (!(curr_table->select->cond=
2414
new Item_cond_and(curr_table->select->cond,
2418
Item_cond_and do not need fix_fields for execution, its parameters
2419
are fixed or do not need fix_fields, too
2421
curr_table->select->cond->quick_fix_field();
2423
curr_table->select_cond= curr_table->select->cond;
2424
curr_table->select_cond->top_level_item();
2425
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
2432
curr_join->select_limit= HA_POS_ERROR;
2436
We can abort sorting after session->select_limit rows if we there is no
2437
WHERE clause for any tables after the sorted one.
2439
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
2440
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
2441
for (; curr_table < end_table ; curr_table++)
2444
table->keyuse is set in the case there was an original WHERE clause
2445
on the table that was optimized away.
2447
if (curr_table->select_cond ||
2448
(curr_table->keyuse && !curr_table->first_inner))
2450
/* We have to sort all rows */
2451
curr_join->select_limit= HA_POS_ERROR;
2456
if (curr_join->join_tab == join_tab && save_join_tab())
2459
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
2460
chose FILESORT to be faster than INDEX SCAN or there is no
2461
suitable index present.
2462
Note, that create_sort_index calls test_if_skip_sort_order and may
2463
finally replace sorting with index scan if there is a LIMIT clause in
2464
the query. XXX: it's never shown in EXPLAIN!
2465
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
2467
if (create_sort_index(session, curr_join,
2468
curr_join->group_list ?
2469
curr_join->group_list : curr_join->order,
2470
curr_join->select_limit,
2471
(select_options & OPTION_FOUND_ROWS ?
2472
HA_POS_ERROR : unit->select_limit_cnt),
2473
curr_join->group_list ? true : false))
2476
sortorder= curr_join->sortorder;
2477
if (curr_join->const_tables != curr_join->tables &&
2478
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
2481
If no IO cache exists for the first table then we are using an
2482
INDEX SCAN and no filesort. Thus we should not remove the sorted
2483
attribute on the INDEX SCAN.
2489
/* XXX: When can we have here session->is_error() not zero? */
2490
if (session->is_error())
2492
error= session->is_error();
2495
curr_join->having= curr_join->tmp_having;
2496
curr_join->fields= curr_fields_list;
2498
session->set_proc_info("Sending data");
2499
result->send_fields(*curr_fields_list,
2500
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2501
error= do_select(curr_join, curr_fields_list, NULL);
2502
session->limit_found_rows= curr_join->send_records;
2504
/* Accumulate the counts from all join iterations of all join parts. */
2505
session->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.
2512
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
2513
set_items_ref_array(items0);
2522
Return error that hold JOIN.
2526
select_lex->join= 0;
2530
if (join_tab != tmp_join->join_tab)
2532
JOIN_TAB *tab, *end;
2533
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
2536
tmp_join->tmp_join= 0;
2537
tmp_table_param.copy_field=0;
2538
return(tmp_join->destroy());
2543
if (exec_tmp_table1)
2544
exec_tmp_table1->free_tmp_table(session);
2545
if (exec_tmp_table2)
2546
exec_tmp_table2->free_tmp_table(session);
2548
delete_dynamic(&keyuse);
2553
297
An entry point to single-unit select (a select without UNION).
3389
859
return(HA_POS_ERROR); /* This shouldn't happend */
3393
This structure is used to collect info on potentially sargable
3394
predicates in order to check whether they become sargable after
3395
reading const tables.
3396
We form a bitmap of indexes that can be used for sargable predicates.
3397
Only such indexes are involved in range analysis.
3399
typedef struct st_sargable_param
3401
Field *field; /* field against which to check sargability */
3402
Item **arg_value; /* values of potential keys for lookups */
3403
uint32_t num_values; /* number of values in the above array */
3407
Calculate the best possible join and initialize the join structure.
3416
make_join_statistics(JOIN *join, TableList *tables, COND *conds,
3417
DYNAMIC_ARRAY *keyuse_array)
3421
uint32_t i,table_count,const_count,key;
3422
table_map found_const_table_map, all_table_map, found_ref, refs;
3423
key_map const_ref, eq_part;
3424
Table **table_vector;
3425
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
3426
KEYUSE *keyuse,*start_keyuse;
3427
table_map outer_join=0;
3428
SARGABLE_PARAM *sargables= 0;
3429
JOIN_TAB *stat_vector[MAX_TABLES+1];
3431
table_count=join->tables;
3432
stat=(JOIN_TAB*) join->session->calloc(sizeof(JOIN_TAB)*table_count);
3433
stat_ref=(JOIN_TAB**) join->session->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
3434
table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
3435
if (!stat || !stat_ref || !table_vector)
3436
return(1); // Eom /* purecov: inspected */
3438
join->best_ref=stat_vector;
3440
stat_end=stat+table_count;
3441
found_const_table_map= all_table_map=0;
3446
s++, tables= tables->next_leaf, i++)
3448
TableList *embedding= tables->embedding;
3451
s->const_keys.reset();
3452
s->checked_keys.reset();
3453
s->needed_reg.reset();
3454
table_vector[i]=s->table=table=tables->table;
3455
table->pos_in_table_list= tables;
3456
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
3459
table->file->print_error(error, MYF(0));
3462
table->quick_keys.reset();
3463
table->reginfo.join_tab=s;
3464
table->reginfo.not_exists_optimize=0;
3465
memset(table->const_key_parts, 0,
3466
sizeof(key_part_map)*table->s->keys);
3467
all_table_map|= table->map;
3469
s->info=0; // For describe
3471
s->dependent= tables->dep_tables;
3472
s->key_dependent= 0;
3473
if (tables->schema_table)
3474
table->file->stats.records= 2;
3475
table->quick_condition_rows= table->file->stats.records;
3477
s->on_expr_ref= &tables->on_expr;
3478
if (*s->on_expr_ref)
3480
/* s is the only inner table of an outer join */
3481
if (!table->file->stats.records && !embedding)
3483
s->dependent= 0; // Ignore LEFT JOIN depend.
3484
set_position(join,const_count++,s,(KEYUSE*) 0);
3487
outer_join|= table->map;
3488
s->embedding_map= 0;
3489
for (;embedding; embedding= embedding->embedding)
3490
s->embedding_map|= embedding->nested_join->nj_map;
3493
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
3495
/* s belongs to a nested join, maybe to several embedded joins */
3496
s->embedding_map= 0;
3499
nested_join_st *nested_join= embedding->nested_join;
3500
s->embedding_map|=nested_join->nj_map;
3501
s->dependent|= embedding->dep_tables;
3502
embedding= embedding->embedding;
3503
outer_join|= nested_join->used_tables;
3508
if ((table->file->stats.records <= 1) &&
3510
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && !join->no_const_tables)
3512
set_position(join,const_count++,s,(KEYUSE*) 0);
3516
join->outer_join=outer_join;
3518
if (join->outer_join)
3521
Build transitive closure for relation 'to be dependent on'.
3522
This will speed up the plan search for many cases with outer joins,
3523
as well as allow us to catch illegal cross references/
3524
Warshall's algorithm is used to build the transitive closure.
3525
As we use bitmaps to represent the relation the complexity
3526
of the algorithm is O((number of tables)^2).
3528
for (i= 0, s= stat ; i < table_count ; i++, s++)
3530
for (uint32_t j= 0 ; j < table_count ; j++)
3532
table= stat[j].table;
3533
if (s->dependent & table->map)
3534
s->dependent |= table->reginfo.join_tab->dependent;
3537
s->table->maybe_null= 1;
3539
/* Catch illegal cross references for outer joins */
3540
for (i= 0, s= stat ; i < table_count ; i++, s++)
3542
if (s->dependent & s->table->map)
3544
join->tables=0; // Don't use join->table
3545
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
3548
s->key_dependent= s->dependent;
3552
if (conds || outer_join)
3553
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
3554
conds, join->cond_equal,
3555
~outer_join, join->select_lex, &sargables))
3558
/* Read tables with 0 or 1 rows (system tables) */
3559
join->const_table_map= 0;
3561
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
3568
join->const_table_map|=s->table->map;
3569
if ((tmp=join_read_const_table(s, p_pos)))
3572
return(1); // Fatal error
3575
found_const_table_map|= s->table->map;
3578
/* loop until no more const tables are found */
3582
more_const_tables_found:
3587
We only have to loop from stat_vector + const_count as
3588
set_position() will move all const_tables first in stat_vector
3591
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
3596
If equi-join condition by a key is null rejecting and after a
3597
substitution of a const table the key value happens to be null
3598
then we can state that there are no matches for this equi-join.
3600
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
3603
When performing an outer join operation if there are no matching rows
3604
for the single row of the outer table all the inner tables are to be
3605
null complemented and thus considered as constant tables.
3606
Here we apply this consideration to the case of outer join operations
3607
with a single inner table only because the case with nested tables
3608
would require a more thorough analysis.
3609
TODO. Apply single row substitution to null complemented inner tables
3610
for nested outer join operations.
3612
while (keyuse->table == table)
3614
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
3615
keyuse->val->is_null() && keyuse->null_rejecting)
3618
table->mark_as_null_row();
3619
found_const_table_map|= table->map;
3620
join->const_table_map|= table->map;
3621
set_position(join,const_count++,s,(KEYUSE*) 0);
3622
goto more_const_tables_found;
3628
if (s->dependent) // If dependent on some table
3630
// All dep. must be constants
3631
if (s->dependent & ~(found_const_table_map))
3633
if (table->file->stats.records <= 1L &&
3634
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
3635
!table->pos_in_table_list->embedding)
3639
join->const_table_map|=table->map;
3640
set_position(join,const_count++,s,(KEYUSE*) 0);
3641
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
3644
return(1); // Fatal error
3647
found_const_table_map|= table->map;
3651
/* check if table can be read by key or table only uses const refs */
3652
if ((keyuse=s->keyuse))
3655
while (keyuse->table == table)
3657
start_keyuse=keyuse;
3659
s->keys.set(key); // QQ: remove this ?
3666
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
3668
if (!((~found_const_table_map) & keyuse->used_tables))
3669
const_ref.set(keyuse->keypart);
3671
refs|=keyuse->used_tables;
3672
eq_part.set(keyuse->keypart);
3675
} while (keyuse->table == table && keyuse->key == key);
3677
if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
3678
!table->pos_in_table_list->embedding)
3680
if ((table->key_info[key].flags & (HA_NOSAME))
3683
if (const_ref == eq_part)
3684
{ // Found everything for ref.
3688
join->const_table_map|= table->map;
3689
set_position(join,const_count++,s,start_keyuse);
3690
if (create_ref_for_key(join, s, start_keyuse,
3691
found_const_table_map))
3693
if ((tmp=join_read_const_table(s,
3694
join->positions+const_count-1)))
3697
return(1); // Fatal error
3700
found_const_table_map|= table->map;
3704
found_ref|= refs; // Table is const if all refs are const
3706
else if (const_ref == eq_part)
3707
s->const_keys.set(key);
3712
} while (join->const_table_map & found_ref && ref_changed);
3715
Update info on indexes that can be used for search lookups as
3716
reading const tables may has added new sargable predicates.
3718
if (const_count && sargables)
3720
for( ; sargables->field ; sargables++)
3722
Field *field= sargables->field;
3723
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
3724
key_map possible_keys= field->key_start;
3725
possible_keys&= field->table->keys_in_use_for_query;
3727
for (uint32_t j=0; j < sargables->num_values; j++)
3728
is_const&= sargables->arg_value[j]->const_item();
3730
join_tab[0].const_keys|= possible_keys;
3734
if (pull_out_semijoin_tables(join))
3737
/* Calc how many (possible) matched records in each table */
3739
for (s=stat ; s < stat_end ; s++)
3741
if (s->type == JT_SYSTEM || s->type == JT_CONST)
3743
/* Only one matching row */
3744
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
3747
/* Approximate found rows and time to read them */
3748
s->found_records=s->records=s->table->file->stats.records;
3749
s->read_time=(ha_rows) s->table->file->scan_time();
3752
Set a max range of how many seeks we can expect when using keys
3753
This is can't be to high as otherwise we are likely to use
3756
s->worst_seeks= cmin((double) s->found_records / 10,
3757
(double) s->read_time*3);
3758
if (s->worst_seeks < 2.0) // Fix for small tables
3762
Add to stat->const_keys those indexes for which all group fields or
3763
all select distinct fields participate in one index.
3765
add_group_and_distinct_keys(join, s);
3767
if (s->const_keys.any() &&
3768
!s->table->pos_in_table_list->embedding)
3772
select= make_select(s->table, found_const_table_map,
3773
found_const_table_map,
3774
*s->on_expr_ref ? *s->on_expr_ref : conds,
3778
records= get_quick_record_count(join->session, select, s->table,
3779
&s->const_keys, join->row_limit);
3780
s->quick=select->quick;
3781
s->needed_reg=select->needed_reg;
3783
if (records == 0 && s->table->reginfo.impossible_range)
3786
Impossible WHERE or ON expression
3787
In case of ON, we mark that the we match one empty NULL row.
3788
In case of WHERE, don't set found_const_table_map to get the
3789
caller to abort with a zero row result.
3791
join->const_table_map|= s->table->map;
3792
set_position(join,const_count++,s,(KEYUSE*) 0);
3794
if (*s->on_expr_ref)
3796
/* Generate empty row */
3797
s->info= "Impossible ON condition";
3798
found_const_table_map|= s->table->map;
3800
s->table->mark_as_null_row(); // All fields are NULL
3803
if (records != HA_POS_ERROR)
3805
s->found_records=records;
3806
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
3812
join->join_tab=stat;
3813
join->map2table=stat_ref;
3814
join->table= join->all_tables=table_vector;
3815
join->const_tables=const_count;
3816
join->found_const_table_map=found_const_table_map;
3818
/* Find an optimal join order of the non-constant tables. */
3819
if (join->const_tables != join->tables)
3821
optimize_keyuse(join, keyuse_array);
3822
if (choose_plan(join, all_table_map & ~join->const_table_map))
3827
memcpy(join->best_positions, join->positions,
3828
sizeof(POSITION)*join->const_tables);
3829
join->best_read=1.0;
3831
/* Generate an execution plan from the found optimal join order. */
3832
return(join->session->killed || get_best_combination(join));
3836
862
/*****************************************************************************
3837
863
Check with keys are used and with tables references with tables
3838
864
Updates in stat:
4894
Find the best access path for an extension of a partial execution
4895
plan and add this path to the plan.
4897
The function finds the best access path to table 's' from the passed
4898
partial plan where an access path is the general term for any means to
4899
access the data in 's'. An access path may use either an index or a scan,
4900
whichever is cheaper. The input partial plan is passed via the array
4901
'join->positions' of length 'idx'. The chosen access method for 's' and its
4902
cost are stored in 'join->positions[idx]'.
4904
@param join pointer to the structure providing all context info
4906
@param s the table to be joined by the function
4907
@param session thread for the connection that submitted the query
4908
@param remaining_tables set of tables not included into the partial plan yet
4909
@param idx the length of the partial plan
4910
@param record_count estimate for the number of records returned by the
4912
@param read_time the cost of the partial plan
4919
best_access_path(JOIN *join,
4922
table_map remaining_tables,
4924
double record_count,
4927
KEYUSE *best_key= 0;
4928
uint32_t best_max_key_part= 0;
4929
bool found_constraint= 0;
4930
double best= DBL_MAX;
4931
double best_time= DBL_MAX;
4932
double records= DBL_MAX;
4933
table_map best_ref_depends_map= 0;
4936
uint32_t best_is_sj_inside_out= 0;
4939
{ /* Use key if possible */
4940
Table *table= s->table;
4941
KEYUSE *keyuse,*start_key=0;
4942
double best_records= DBL_MAX;
4943
uint32_t max_key_part=0;
4944
uint64_t bound_sj_equalities= 0;
4945
bool try_sj_inside_out= false;
4947
Discover the bound equalites. We need to do this, if
4948
1. The next table is an SJ-inner table, and
4949
2. It is the first table from that semijoin, and
4950
3. We're not within a semi-join range (i.e. all semi-joins either have
4951
all or none of their tables in join_table_map), except
4952
s->emb_sj_nest (which we've just entered).
4953
3. All correlation references from this sj-nest are bound
4955
if (s->emb_sj_nest && // (1)
4956
s->emb_sj_nest->sj_in_exprs < 64 &&
4957
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
4958
s->emb_sj_nest->sj_inner_tables) && // (2)
4959
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
4960
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
4962
/* This table is an InsideOut scan candidate */
4963
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
4965
try_sj_inside_out= true;
4968
/* Test how we can use keys */
4969
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
4970
for (keyuse=s->keyuse ; keyuse->table == table ;)
4972
key_part_map found_part= 0;
4973
table_map found_ref= 0;
4974
uint32_t key= keyuse->key;
4975
KEY *keyinfo= table->key_info+key;
4976
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
4977
key_part_map const_part= 0;
4978
/* The or-null keypart in ref-or-null access: */
4979
key_part_map ref_or_null_part= 0;
4981
/* Calculate how many key segments of the current key we can use */
4983
uint64_t handled_sj_equalities=0;
4984
key_part_map sj_insideout_map= 0;
4986
do /* For each keypart */
4988
uint32_t keypart= keyuse->keypart;
4989
table_map best_part_found_ref= 0;
4990
double best_prev_record_reads= DBL_MAX;
4992
do /* For each way to access the keypart */
4996
if 1. expression doesn't refer to forward tables
4997
2. we won't get two ref-or-null's
4999
if (!(remaining_tables & keyuse->used_tables) &&
5000
!(ref_or_null_part && (keyuse->optimize &
5001
KEY_OPTIMIZE_REF_OR_NULL)))
5003
found_part|= keyuse->keypart_map;
5004
if (!(keyuse->used_tables & ~join->const_table_map))
5005
const_part|= keyuse->keypart_map;
5007
double tmp2= prev_record_reads(join, idx, (found_ref |
5008
keyuse->used_tables));
5009
if (tmp2 < best_prev_record_reads)
5011
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
5012
best_prev_record_reads= tmp2;
5014
if (rec > keyuse->ref_table_rows)
5015
rec= keyuse->ref_table_rows;
5017
If there is one 'key_column IS NULL' expression, we can
5018
use this ref_or_null optimisation of this field
5020
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
5021
ref_or_null_part |= keyuse->keypart_map;
5024
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
5026
if (!(remaining_tables & keyuse->used_tables))
5027
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
5030
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
5031
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
5036
} while (keyuse->table == table && keyuse->key == key &&
5037
keyuse->keypart == keypart);
5038
found_ref|= best_part_found_ref;
5039
} while (keyuse->table == table && keyuse->key == key);
5042
Assume that that each key matches a proportional part of table.
5044
if (!found_part && !handled_sj_equalities)
5045
continue; // Nothing usable found
5047
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
5048
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
5050
bool sj_inside_out_scan= false;
5052
found_constraint= 1;
5054
Check if InsideOut scan is applicable:
5055
1. All IN-equalities are either "bound" or "handled"
5056
2. Index keyparts are
5059
if (try_sj_inside_out &&
5060
table->covering_keys.test(key) &&
5061
(handled_sj_equalities | bound_sj_equalities) == // (1)
5062
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
5064
uint32_t n_fixed_parts= max_part_bit(found_part);
5065
if (n_fixed_parts != keyinfo->key_parts &&
5066
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
5067
PREV_BITS(uint, keyinfo->key_parts))
5070
Not all parts are fixed. Produce bitmap of remaining bits and
5071
check if all of them are covered.
5073
sj_inside_out_scan= true;
5077
It's a confluent ref scan.
5079
That is, all found KEYUSE elements refer to IN-equalities,
5080
and there is really no ref access because there is no
5081
t.keypart0 = {bound expression}
5083
Calculate the cost of complete loose index scan.
5085
records= (double)s->table->file->stats.records;
5087
/* The cost is entire index scan cost (divided by 2) */
5088
best_time= s->table->file->index_only_read_time(key, records);
5090
/* Now figure how many different keys we will get */
5092
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
5093
records= records / rpc;
5100
Check if we found full key
5102
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
5105
max_key_part= UINT32_MAX;
5106
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
5108
tmp = prev_record_reads(join, idx, found_ref);
5114
{ /* We found a const key */
5116
ReuseRangeEstimateForRef-1:
5117
We get here if we've found a ref(const) (c_i are constants):
5118
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
5120
If range optimizer was able to construct a "range"
5121
access on this index, then its condition "quick_cond" was
5122
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
5123
from the range optimizer.
5125
Proof of (*): By properties of range and ref optimizers
5126
quick_cond will be equal or tighther than ref_const_cond.
5127
ref_const_cond already covers "smallest" possible interval -
5128
a singlepoint interval over all keyparts. Therefore,
5129
quick_cond is equivalent to ref_const_cond (if it was an
5130
empty interval we wouldn't have got here).
5132
if (table->quick_keys.test(key))
5133
records= (double) table->quick_rows[key];
5136
/* quick_range couldn't use key! */
5137
records= (double) s->records/rec;
5142
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
5143
{ /* Prefer longer keys */
5145
((double) s->records / (double) rec *
5147
((double) (table->s->max_key_length-keyinfo->key_length) /
5148
(double) table->s->max_key_length)));
5150
records=2.0; /* Can't be as good as a unique */
5153
ReuseRangeEstimateForRef-2: We get here if we could not reuse
5154
E(#rows) from range optimizer. Make another try:
5156
If range optimizer produced E(#rows) for a prefix of the ref
5157
access we're considering, and that E(#rows) is lower then our
5158
current estimate, make an adjustment. The criteria of when we
5159
can make an adjustment is a special case of the criteria used
5160
in ReuseRangeEstimateForRef-3.
5162
if (table->quick_keys.test(key) &&
5163
const_part & (1 << table->quick_key_parts[key]) &&
5164
table->quick_n_ranges[key] == 1 &&
5165
records > (double) table->quick_rows[key])
5167
records= (double) table->quick_rows[key];
5170
/* Limit the number of matched rows */
5172
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5173
if (table->covering_keys.test(key))
5175
/* we can use only index tree */
5176
tmp= record_count * table->file->index_only_read_time(key, tmp);
5179
tmp= record_count*cmin(tmp,s->worst_seeks);
5185
Use as much key-parts as possible and a uniq key is better
5186
than a not unique key
5187
Set tmp to (previous record count) * (records / combination)
5189
if ((found_part & 1) &&
5190
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
5191
found_part == PREV_BITS(uint,keyinfo->key_parts)))
5193
max_key_part= max_part_bit(found_part);
5195
ReuseRangeEstimateForRef-3:
5196
We're now considering a ref[or_null] access via
5197
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
5198
(same-as-above but with one cond replaced
5199
with "t.keypart_i IS NULL")] (**)
5201
Try re-using E(#rows) from "range" optimizer:
5202
We can do so if "range" optimizer used the same intervals as
5203
in (**). The intervals used by range optimizer may be not
5204
available at this point (as "range" access might have choosen to
5205
create quick select over another index), so we can't compare
5206
them to (**). We'll make indirect judgements instead.
5207
The sufficient conditions for re-use are:
5208
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
5209
this is not satisfied we have no way to know which ranges
5210
will be actually scanned by 'ref' until we execute the
5212
(C2) max #key parts in 'range' access == K == max_key_part (this
5213
is apparently a necessary requirement)
5215
We also have a property that "range optimizer produces equal or
5216
tighter set of scan intervals than ref(const) optimizer". Each
5217
of the intervals in (**) are "tightest possible" intervals when
5218
one limits itself to using keyparts 1..K (which we do in #2).
5219
From here it follows that range access used either one, or
5220
both of the (I1) and (I2) intervals:
5222
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
5223
(same-as-above but with one cond replaced
5224
with "t.keypart_i IS NULL") (I2)
5226
The remaining part is to exclude the situation where range
5227
optimizer used one interval while we're considering
5228
ref-or-null and looking for estimate for two intervals. This
5229
is done by last limitation:
5231
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
5233
if (table->quick_keys.test(key) && !found_ref && //(C1)
5234
table->quick_key_parts[key] == max_key_part && //(C2)
5235
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
5237
tmp= records= (double) table->quick_rows[key];
5241
/* Check if we have statistic about the distribution */
5242
if ((records= keyinfo->rec_per_key[max_key_part-1]))
5245
Fix for the case where the index statistics is too
5247
(1) We're considering ref(const) and there is quick select
5249
(2) and that quick select uses more keyparts (i.e. it will
5250
scan equal/smaller interval then this ref(const))
5251
(3) and E(#rows) for quick select is higher then our
5254
We'll use E(#rows) from quick select.
5256
Q: Why do we choose to use 'ref'? Won't quick select be
5257
cheaper in some cases ?
5258
TODO: figure this out and adjust the plan choice if needed.
5260
if (!found_ref && table->quick_keys.test(key) && // (1)
5261
table->quick_key_parts[key] > max_key_part && // (2)
5262
records < (double)table->quick_rows[key]) // (3)
5263
records= (double)table->quick_rows[key];
5270
Assume that the first key part matches 1% of the file
5271
and that the whole key matches 10 (duplicates) or 1
5273
Assume also that more key matches proportionally more
5275
This gives the formula:
5276
records = (x * (b-a) + a*c-b)/(c-1)
5278
b = records matched by whole key
5279
a = records matched by first key part (1% of all records?)
5280
c = number of key parts in key
5281
x = used key parts (1 <= x <= c)
5284
if (!(rec_per_key=(double)
5285
keyinfo->rec_per_key[keyinfo->key_parts-1]))
5286
rec_per_key=(double) s->records/rec+1;
5290
else if (rec_per_key/(double) s->records >= 0.01)
5294
double a=s->records*0.01;
5295
if (keyinfo->key_parts > 1)
5296
tmp= (max_key_part * (rec_per_key - a) +
5297
a*keyinfo->key_parts - rec_per_key)/
5298
(keyinfo->key_parts-1);
5301
set_if_bigger(tmp,1.0);
5303
records = (uint32_t) tmp;
5306
if (ref_or_null_part)
5308
/* We need to do two key searches to find key */
5314
ReuseRangeEstimateForRef-4: We get here if we could not reuse
5315
E(#rows) from range optimizer. Make another try:
5317
If range optimizer produced E(#rows) for a prefix of the ref
5318
access we're considering, and that E(#rows) is lower then our
5319
current estimate, make the adjustment.
5321
The decision whether we can re-use the estimate from the range
5322
optimizer is the same as in ReuseRangeEstimateForRef-3,
5323
applied to first table->quick_key_parts[key] key parts.
5325
if (table->quick_keys.test(key) &&
5326
table->quick_key_parts[key] <= max_key_part &&
5327
const_part & (1 << table->quick_key_parts[key]) &&
5328
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
5329
const_part) ? 1 : 0) &&
5330
records > (double) table->quick_rows[key])
5332
tmp= records= (double) table->quick_rows[key];
5336
/* Limit the number of matched rows */
5337
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5338
if (table->covering_keys.test(key))
5340
/* we can use only index tree */
5341
tmp= record_count * table->file->index_only_read_time(key, tmp);
5344
tmp= record_count * cmin(tmp,s->worst_seeks);
5347
tmp= best_time; // Do nothing
5350
if (sj_inside_out_scan && !start_key)
5358
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
5360
best_time= tmp + records/(double) TIME_FOR_COMPARE;
5362
best_records= records;
5363
best_key= start_key;
5364
best_max_key_part= max_key_part;
5365
best_ref_depends_map= found_ref;
5366
best_is_sj_inside_out= sj_inside_out_scan;
5369
records= best_records;
5373
Don't test table scan if it can't be better.
5374
Prefer key lookup if we would use the same key for scanning.
5376
Don't do a table scan on InnoDB tables, if we can read the used
5377
parts of the row from any of the used index.
5378
This is because table scans uses index and we would not win
5379
anything by using a table scan.
5381
A word for word translation of the below if-statement in sergefp's
5382
understanding: we check if we should use table scan if:
5383
(1) The found 'ref' access produces more records than a table scan
5384
(or index scan, or quick select), or 'ref' is more expensive than
5386
(2) This doesn't hold: the best way to perform table scan is to to perform
5387
'range' access using index IDX, and the best way to perform 'ref'
5388
access is to use the same index IDX, with the same or more key parts.
5389
(note: it is not clear how this rule is/should be extended to
5390
index_merge quick selects)
5391
(3) See above note about InnoDB.
5392
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
5393
path, but there is no quick select)
5394
If the condition in the above brackets holds, then the only possible
5395
"table scan" access method is ALL/index (there is no quick select).
5396
Since we have a 'ref' access path, and FORCE INDEX instructs us to
5397
choose it over ALL/index, there is no need to consider a full table
5400
if ((records >= s->found_records || best > s->read_time) && // (1)
5401
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
5402
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
5403
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
5404
! s->table->covering_keys.none() && best_key && !s->quick) &&// (3)
5405
!(s->table->force_index && best_key && !s->quick)) // (4)
5406
{ // Check full join
5407
ha_rows rnd_records= s->found_records;
5409
If there is a filtering condition on the table (i.e. ref analyzer found
5410
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
5411
preceding this table in the join order we're now considering), then
5412
assume that 25% of the rows will be filtered out by this condition.
5414
This heuristic is supposed to force tables used in exprZ to be before
5415
this table in join order.
5417
if (found_constraint)
5418
rnd_records-= rnd_records/4;
5421
If applicable, get a more accurate estimate. Don't use the two
5424
if (s->table->quick_condition_rows != s->found_records)
5425
rnd_records= s->table->quick_condition_rows;
5428
Range optimizer never proposes a RANGE if it isn't better
5429
than FULL: so if RANGE is present, it's always preferred to FULL.
5430
Here we estimate its cost.
5436
- read record range through 'quick'
5437
- skip rows which does not satisfy WHERE constraints
5439
We take into account possible use of join cache for ALL/index
5440
access (see first else-branch below), but we don't take it into
5441
account here for range/index_merge access. Find out why this is so.
5444
(s->quick->read_time +
5445
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
5449
/* Estimate cost of reading table. */
5450
tmp= s->table->file->scan_time();
5451
if (s->table->map & join->outer_join) // Can't use join cache
5454
For each record we have to:
5455
- read the whole table record
5456
- skip rows which does not satisfy join condition
5460
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
5464
/* We read the table as many times as join buffer becomes full. */
5465
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
5467
(double) session->variables.join_buff_size));
5469
We don't make full cartesian product between rows in the scanned
5470
table and existing records because we skip all rows from the
5471
scanned table, which does not satisfy join condition when
5472
we read the table (see flush_cached_records for details). Here we
5473
take into account cost to read and skip these records.
5475
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
5480
We estimate the cost of evaluating WHERE clause for found records
5481
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
5482
tmp give us total cost of using Table SCAN
5484
if (best == DBL_MAX ||
5485
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
5486
best + record_count/(double) TIME_FOR_COMPARE*records))
5489
If the table has a range (s->quick is set) make_join_select()
5490
will ensure that this will be used
5493
records= rows2double(rnd_records);
5495
/* range/index_merge/ALL/index access method are "independent", so: */
5496
best_ref_depends_map= 0;
5497
best_is_sj_inside_out= false;
5501
/* Update the cost information for the current partial plan */
5502
join->positions[idx].records_read= records;
5503
join->positions[idx].read_time= best;
5504
join->positions[idx].key= best_key;
5505
join->positions[idx].table= s;
5506
join->positions[idx].ref_depend_map= best_ref_depends_map;
5507
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
5510
idx == join->const_tables &&
5511
s->table == join->sort_by_table &&
5512
join->unit->select_limit_cnt >= records)
5513
join->sort_by_table= (Table*) 1; // Must use temporary table
5520
Selects and invokes a search strategy for an optimal query plan.
5522
The function checks user-configurable parameters that control the search
5523
strategy for an optimal plan, selects the search method and then invokes
5524
it. Each specific optimization procedure stores the final optimal plan in
5525
the array 'join->best_positions', and the cost of the plan in
5528
@param join pointer to the structure providing all context info for
5530
@param join_tables set of the tables in the query
5533
'MAX_TABLES+2' denotes the old implementation of find_best before
5534
the greedy version. Will be removed when greedy_search is approved.
5543
choose_plan(JOIN *join, table_map join_tables)
5545
uint32_t search_depth= join->session->variables.optimizer_search_depth;
5546
uint32_t prune_level= join->session->variables.optimizer_prune_level;
5547
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
5549
join->cur_embedding_map= 0;
5550
reset_nj_counters(join->join_list);
5552
if (SELECT_STRAIGHT_JOIN option is set)
5553
reorder tables so dependent tables come after tables they depend
5554
on, otherwise keep tables in the order they were specified in the query
5556
Apply heuristic: pre-sort all access plans with respect to the number of
5559
my_qsort(join->best_ref + join->const_tables,
5560
join->tables - join->const_tables, sizeof(JOIN_TAB*),
5561
straight_join ? join_tab_cmp_straight : join_tab_cmp);
5562
join->cur_emb_sj_nests= 0;
5565
optimize_straight_join(join, join_tables);
5569
if (search_depth == MAX_TABLES+2)
5571
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
5572
the greedy version. Will be removed when greedy_search is approved.
5574
join->best_read= DBL_MAX;
5575
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
5580
if (search_depth == 0)
5581
/* Automatically determine a reasonable value for 'search_depth' */
5582
search_depth= determine_search_depth(join);
5583
if (greedy_search(join, join_tables, search_depth, prune_level))
5589
Store the cost of this query into a user variable
5590
Don't update last_query_cost for statements that are not "flat joins" :
5591
i.e. they have subqueries, unions or call stored procedures.
5592
TODO: calculate a correct cost for a query with subqueries and UNIONs.
5594
if (join->session->lex->is_single_level_stmt())
5595
join->session->status_var.last_query_cost= join->best_read;
5601
1871
Compare two JOIN_TAB objects based on the number of accessed records.
5659
Heuristic procedure to automatically guess a reasonable degree of
5660
exhaustiveness for the greedy search procedure.
5662
The procedure estimates the optimization time and selects a search depth
5663
big enough to result in a near-optimal QEP, that doesn't take too long to
5664
find. If the number of tables in the query exceeds some constant, then
5665
search_depth is set to this constant.
5667
@param join pointer to the structure providing all context info for
5671
This is an extremely simplistic implementation that serves as a stub for a
5672
more advanced analysis of the join. Ideally the search depth should be
5673
determined by learning from previous query optimizations, because it will
5674
depend on the CPU power (and other factors).
5677
this value should be determined dynamically, based on statistics:
5678
uint32_t max_tables_for_exhaustive_opt= 7;
5681
this value could be determined by some mapping of the form:
5682
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5685
A positive integer that specifies the search depth (and thus the
5686
exhaustiveness) of the depth-first search algorithm used by
5691
determine_search_depth(JOIN *join)
5693
uint32_t table_count= join->tables - join->const_tables;
5694
uint32_t search_depth;
5695
/* TODO: this value should be determined dynamically, based on statistics: */
5696
uint32_t max_tables_for_exhaustive_opt= 7;
5698
if (table_count <= max_tables_for_exhaustive_opt)
5699
search_depth= table_count+1; // use exhaustive for small number of tables
5702
TODO: this value could be determined by some mapping of the form:
5703
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5705
search_depth= max_tables_for_exhaustive_opt; // use greedy search
5707
return search_depth;
5712
Select the best ways to access the tables in a query without reordering them.
5714
Find the best access paths for each query table and compute their costs
5715
according to their order in the array 'join->best_ref' (thus without
5716
reordering the join tables). The function calls sequentially
5717
'best_access_path' for each table in the query to select the best table
5718
access method. The final optimal plan is stored in the array
5719
'join->best_positions', and the corresponding cost in 'join->best_read'.
5721
@param join pointer to the structure providing all context info for
5723
@param join_tables set of the tables in the query
5726
This function can be applied to:
5727
- queries with STRAIGHT_JOIN
5728
- internally to compute the cost of an arbitrary QEP
5730
Thus 'optimize_straight_join' can be used at any stage of the query
5731
optimization process to finalize a QEP as it is.
5735
optimize_straight_join(JOIN *join, table_map join_tables)
5738
uint32_t idx= join->const_tables;
5739
double record_count= 1.0;
5740
double read_time= 0.0;
5742
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
5744
/* Find the best access method from 's' to the current partial plan */
5745
advance_sj_state(join_tables, s);
5746
best_access_path(join, s, join->session, join_tables, idx,
5747
record_count, read_time);
5748
/* compute the cost of the new plan extended with 's' */
5749
record_count*= join->positions[idx].records_read;
5750
read_time+= join->positions[idx].read_time;
5751
join_tables&= ~(s->table->map);
5755
read_time+= record_count / (double) TIME_FOR_COMPARE;
5756
if (join->sort_by_table &&
5757
join->sort_by_table != join->positions[join->const_tables].table->table)
5758
read_time+= record_count; // We have to make a temp table
5759
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
5760
join->best_read= read_time;
5765
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
5767
The search procedure uses a hybrid greedy/exhaustive search with controlled
5768
exhaustiveness. The search is performed in N = card(remaining_tables)
5769
steps. Each step evaluates how promising is each of the unoptimized tables,
5770
selects the most promising table, and extends the current partial QEP with
5771
that table. Currenly the most 'promising' table is the one with least
5772
expensive extension.\
5774
There are two extreme cases:
5775
-# When (card(remaining_tables) < search_depth), the estimate finds the
5776
best complete continuation of the partial QEP. This continuation can be
5777
used directly as a result of the search.
5778
-# When (search_depth == 1) the 'best_extension_by_limited_search'
5779
consideres the extension of the current QEP with each of the remaining
5782
All other cases are in-between these two extremes. Thus the parameter
5783
'search_depth' controlls the exhaustiveness of the search. The higher the
5784
value, the longer the optimizaton time and possibly the better the
5785
resulting plan. The lower the value, the fewer alternative plans are
5786
estimated, but the more likely to get a bad QEP.
5788
All intermediate and final results of the procedure are stored in 'join':
5789
- join->positions : modified for every partial QEP that is explored
5790
- join->best_positions: modified for the current best complete QEP
5791
- join->best_read : modified for the current best complete QEP
5792
- join->best_ref : might be partially reordered
5794
The final optimal plan is stored in 'join->best_positions', and its
5795
corresponding cost in 'join->best_read'.
5798
The following pseudocode describes the algorithm of 'greedy_search':
5801
procedure greedy_search
5802
input: remaining_tables
5807
(t, a) = best_extension(pplan, remaining_tables);
5808
pplan = concat(pplan, (t, a));
5809
remaining_tables = remaining_tables - t;
5810
} while (remaining_tables != {})
5815
where 'best_extension' is a placeholder for a procedure that selects the
5816
most "promising" of all tables in 'remaining_tables'.
5817
Currently this estimate is performed by calling
5818
'best_extension_by_limited_search' to evaluate all extensions of the
5819
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
5820
mainly depends on that of 'best_extension_by_limited_search'.
5823
If 'best_extension()' == 'best_extension_by_limited_search()', then the
5824
worst-case complexity of this algorithm is <=
5825
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
5826
complexity of greedy_search is O(N!).
5829
In the future, 'greedy_search' might be extended to support other
5830
implementations of 'best_extension', e.g. some simpler quadratic procedure.
5832
@param join pointer to the structure providing all context info
5834
@param remaining_tables set of tables not included into the partial plan yet
5835
@param search_depth controlls the exhaustiveness of the search
5836
@param prune_level the pruning heuristics that should be applied during
5846
greedy_search(JOIN *join,
5847
table_map remaining_tables,
5848
uint32_t search_depth,
5849
uint32_t prune_level)
5851
double record_count= 1.0;
5852
double read_time= 0.0;
5853
uint32_t idx= join->const_tables; // index into 'join->best_ref'
5855
uint32_t size_remain; // cardinality of remaining_tables
5857
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
5859
/* number of tables that remain to be optimized */
5860
size_remain= my_count_bits(remaining_tables);
5863
/* Find the extension of the current QEP with the lowest cost */
5864
join->best_read= DBL_MAX;
5865
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
5866
read_time, search_depth, prune_level))
5869
if (size_remain <= search_depth)
5872
'join->best_positions' contains a complete optimal extension of the
5873
current partial QEP.
5878
/* select the first table in the optimal extension as most promising */
5879
best_pos= join->best_positions[idx];
5880
best_table= best_pos.table;
5882
Each subsequent loop of 'best_extension_by_limited_search' uses
5883
'join->positions' for cost estimates, therefore we have to update its
5886
join->positions[idx]= best_pos;
5888
/* find the position of 'best_table' in 'join->best_ref' */
5890
JOIN_TAB *pos= join->best_ref[best_idx];
5891
while (pos && best_table != pos)
5892
pos= join->best_ref[++best_idx];
5893
assert((pos != NULL)); // should always find 'best_table'
5894
/* move 'best_table' at the first free position in the array of joins */
5895
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
5897
/* compute the cost of the new plan extended with 'best_table' */
5898
record_count*= join->positions[idx].records_read;
5899
read_time+= join->positions[idx].read_time;
5901
remaining_tables&= ~(best_table->table->map);
5909
Find a good, possibly optimal, query execution plan (QEP) by a possibly
5912
The procedure searches for the optimal ordering of the query tables in set
5913
'remaining_tables' of size N, and the corresponding optimal access paths to
5914
each table. The choice of a table order and an access path for each table
5915
constitutes a query execution plan (QEP) that fully specifies how to
5918
The maximal size of the found plan is controlled by the parameter
5919
'search_depth'. When search_depth == N, the resulting plan is complete and
5920
can be used directly as a QEP. If search_depth < N, the found plan consists
5921
of only some of the query tables. Such "partial" optimal plans are useful
5922
only as input to query optimization procedures, and cannot be used directly
5925
The algorithm begins with an empty partial plan stored in 'join->positions'
5926
and a set of N tables - 'remaining_tables'. Each step of the algorithm
5927
evaluates the cost of the partial plan extended by all access plans for
5928
each of the relations in 'remaining_tables', expands the current partial
5929
plan with the access plan that results in lowest cost of the expanded
5930
partial plan, and removes the corresponding relation from
5931
'remaining_tables'. The algorithm continues until it either constructs a
5932
complete optimal plan, or constructs an optimal plartial plan with size =
5935
The final optimal plan is stored in 'join->best_positions'. The
5936
corresponding cost of the optimal plan is in 'join->best_read'.
5939
The procedure uses a recursive depth-first search where the depth of the
5940
recursion (and thus the exhaustiveness of the search) is controlled by the
5941
parameter 'search_depth'.
5944
The pseudocode below describes the algorithm of
5945
'best_extension_by_limited_search'. The worst-case complexity of this
5946
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
5947
the complexity of greedy_search is O(N!).
5950
procedure best_extension_by_limited_search(
5951
pplan in, // in, partial plan of tables-joined-so-far
5952
pplan_cost, // in, cost of pplan
5953
remaining_tables, // in, set of tables not referenced in pplan
5954
best_plan_so_far, // in/out, best plan found so far
5955
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5956
search_depth) // in, maximum size of the plans being considered
5958
for each table T from remaining_tables
5960
// Calculate the cost of using table T as above
5961
cost = complex-series-of-calculations;
5963
// Add the cost to the cost so far.
5966
if (pplan_cost >= best_plan_so_far_cost)
5967
// pplan_cost already too great, stop search
5970
pplan= expand pplan by best_access_method;
5971
remaining_tables= remaining_tables - table T;
5972
if (remaining_tables is not an empty set
5976
best_extension_by_limited_search(pplan, pplan_cost,
5979
best_plan_so_far_cost,
5984
best_plan_so_far_cost= pplan_cost;
5985
best_plan_so_far= pplan;
5992
When 'best_extension_by_limited_search' is called for the first time,
5993
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
5994
The actual implementation provides a way to optionally use pruning
5995
heuristic (controlled by the parameter 'prune_level') to reduce the search
5996
space by skipping some partial plans.
5999
The parameter 'search_depth' provides control over the recursion
6000
depth, and thus the size of the resulting optimal plan.
6002
@param join pointer to the structure providing all context info
6004
@param remaining_tables set of tables not included into the partial plan yet
6005
@param idx length of the partial QEP in 'join->positions';
6006
since a depth-first search is used, also corresponds
6007
to the current depth of the search tree;
6008
also an index in the array 'join->best_ref';
6009
@param record_count estimate for the number of records returned by the
6011
@param read_time the cost of the best partial plan
6012
@param search_depth maximum depth of the recursion and thus size of the
6014
(0 < search_depth <= join->tables+1).
6015
@param prune_level pruning heuristics that should be applied during
6017
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
6026
best_extension_by_limited_search(JOIN *join,
6027
table_map remaining_tables,
6029
double record_count,
6031
uint32_t search_depth,
6032
uint32_t prune_level)
6034
Session *session= join->session;
6035
if (session->killed) // Abort
6039
'join' is a partial plan with lower cost than the best plan so far,
6040
so continue expanding it further with the tables in 'remaining_tables'.
6043
double best_record_count= DBL_MAX;
6044
double best_read_time= DBL_MAX;
6046
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
6048
table_map real_table_bit= s->table->map;
6049
if ((remaining_tables & real_table_bit) &&
6050
!(remaining_tables & s->dependent) &&
6051
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6053
double current_record_count, current_read_time;
6054
advance_sj_state(remaining_tables, s);
6057
psergey-insideout-todo:
6058
when best_access_path() detects it could do an InsideOut scan or
6059
some other scan, have it return an insideout scan and a flag that
6060
requests to "fork" this loop iteration. (Q: how does that behave
6061
when the depth is insufficient??)
6063
/* Find the best access method from 's' to the current partial plan */
6064
best_access_path(join, s, session, remaining_tables, idx,
6065
record_count, read_time);
6066
/* Compute the cost of extending the plan with 's' */
6067
current_record_count= record_count * join->positions[idx].records_read;
6068
current_read_time= read_time + join->positions[idx].read_time;
6070
/* Expand only partial plans with lower cost than the best QEP so far */
6071
if ((current_read_time +
6072
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
6074
restore_prev_nj_state(s);
6075
restore_prev_sj_state(remaining_tables, s);
6080
Prune some less promising partial plans. This heuristic may miss
6081
the optimal QEPs, thus it results in a non-exhaustive search.
6083
if (prune_level == 1)
6085
if (best_record_count > current_record_count ||
6086
best_read_time > current_read_time ||
6087
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
6089
if (best_record_count >= current_record_count &&
6090
best_read_time >= current_read_time &&
6091
/* TODO: What is the reasoning behind this condition? */
6092
(!(s->key_dependent & remaining_tables) ||
6093
join->positions[idx].records_read < 2.0))
6095
best_record_count= current_record_count;
6096
best_read_time= current_read_time;
6101
restore_prev_nj_state(s);
6102
restore_prev_sj_state(remaining_tables, s);
6107
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
6108
{ /* Recursively expand the current partial plan */
6109
std::swap(join->best_ref[idx], *pos);
6110
if (best_extension_by_limited_search(join,
6111
remaining_tables & ~real_table_bit,
6113
current_record_count,
6118
std::swap(join->best_ref[idx], *pos);
6122
'join' is either the best partial QEP with 'search_depth' relations,
6123
or the best complete QEP so far, whichever is smaller.
6125
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
6126
if (join->sort_by_table &&
6127
join->sort_by_table !=
6128
join->positions[join->const_tables].table->table)
6129
/* We have to make a temp table */
6130
current_read_time+= current_record_count;
6131
if ((search_depth == 1) || (current_read_time < join->best_read))
6133
memcpy(join->best_positions, join->positions,
6134
sizeof(POSITION) * (idx + 1));
6135
join->best_read= current_read_time - 0.001;
6138
restore_prev_nj_state(s);
6139
restore_prev_sj_state(remaining_tables, s);
6148
- TODO: this function is here only temporarily until 'greedy_search' is
6149
tested and accepted.
6156
find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count,
6159
Session *session= join->session;
6160
if (session->killed)
6164
read_time+=record_count/(double) TIME_FOR_COMPARE;
6165
if (join->sort_by_table &&
6166
join->sort_by_table !=
6167
join->positions[join->const_tables].table->table)
6168
read_time+=record_count; // We have to make a temp table
6169
if (read_time < join->best_read)
6171
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
6172
join->best_read= read_time - 0.001;
6176
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
6177
return(false); /* Found better before */
6180
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
6181
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
6183
table_map real_table_bit=s->table->map;
6184
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
6185
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6187
double records, best;
6188
advance_sj_state(rest_tables, s);
6189
best_access_path(join, s, session, rest_tables, idx, record_count,
6191
records= join->positions[idx].records_read;
6192
best= join->positions[idx].read_time;
6194
Go to the next level only if there hasn't been a better key on
6195
this level! This will cut down the search for a lot simple cases!
6197
double current_record_count=record_count*records;
6198
double current_read_time=read_time+best;
6199
if (best_record_count > current_record_count ||
6200
best_read_time > current_read_time ||
6201
(idx == join->const_tables && s->table == join->sort_by_table))
6203
if (best_record_count >= current_record_count &&
6204
best_read_time >= current_read_time &&
6205
(!(s->key_dependent & rest_tables) || records < 2.0))
6207
best_record_count=current_record_count;
6208
best_read_time=current_read_time;
6210
std::swap(join->best_ref[idx], *pos);
6211
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
6212
current_record_count,current_read_time))
6214
std::swap(join->best_ref[idx], *pos);
6216
restore_prev_nj_state(s);
6217
restore_prev_sj_state(rest_tables, s);
6218
if (join->select_options & SELECT_STRAIGHT_JOIN)
6219
break; // Don't test all combinations
6227
1926
Find how much space the prevous read not const tables takes in cache.
6230
static void calc_used_field_length(Session *, JOIN_TAB *join_tab)
1928
void calc_used_field_length(Session *, JOIN_TAB *join_tab)
6232
1930
uint32_t null_fields,blobs,fields,rec_length;
6233
1931
Field **f_ptr,*field;
6828
Fill in outer join related info for the execution plan structure.
6830
For each outer join operation left after simplification of the
6831
original query the function set up the following pointers in the linear
6832
structure join->join_tab representing the selected execution plan.
6833
The first inner table t0 for the operation is set to refer to the last
6834
inner table tk through the field t0->last_inner.
6835
Any inner table ti for the operation are set to refer to the first
6836
inner table ti->first_inner.
6837
The first inner table t0 for the operation is set to refer to the
6838
first inner table of the embedding outer join operation, if there is any,
6839
through the field t0->first_upper.
6840
The on expression for the outer join operation is attached to the
6841
corresponding first inner table through the field t0->on_expr_ref.
6842
Here ti are structures of the JOIN_TAB type.
6844
EXAMPLE. For the query:
6848
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
6849
ON (t1.a=t2.a AND t1.b=t3.b)
6853
given the execution plan with the table order t1,t2,t3,t4
6854
is selected, the following references will be set;
6855
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
6856
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
6857
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
6858
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
6860
@param join reference to the info fully describing the query
6863
The function assumes that the simplification procedure has been
6864
already applied to the join query (see simplify_joins).
6865
This function can be called only after the execution plan
6870
make_outerjoin_info(JOIN *join)
6872
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6874
JOIN_TAB *tab=join->join_tab+i;
6875
Table *table=tab->table;
6876
TableList *tbl= table->pos_in_table_list;
6877
TableList *embedding= tbl->embedding;
6879
if (tbl->outer_join)
6882
Table tab is the only one inner table for outer join.
6883
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
6884
is in the query above.)
6886
tab->last_inner= tab->first_inner= tab;
6887
tab->on_expr_ref= &tbl->on_expr;
6888
tab->cond_equal= tbl->cond_equal;
6890
tab->first_upper= embedding->nested_join->first_nested;
6892
for ( ; embedding ; embedding= embedding->embedding)
6894
/* Ignore sj-nests: */
6895
if (!embedding->on_expr)
6897
nested_join_st *nested_join= embedding->nested_join;
6898
if (!nested_join->counter_)
6901
Table tab is the first inner table for nested_join.
6902
Save reference to it in the nested join structure.
6904
nested_join->first_nested= tab;
6905
tab->on_expr_ref= &embedding->on_expr;
6906
tab->cond_equal= tbl->cond_equal;
6907
if (embedding->embedding)
6908
tab->first_upper= embedding->embedding->nested_join->first_nested;
6910
if (!tab->first_inner)
6911
tab->first_inner= nested_join->first_nested;
6912
if (++nested_join->counter_ < nested_join->join_list.elements)
6914
/* Table tab is the last inner table for nested join. */
6915
nested_join->first_nested->last_inner= tab;
6923
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
6925
Session *session= join->session;
6928
add_not_null_conds(join);
6929
table_map used_tables;
6930
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
6931
{ /* there may be a select without a cond. */
6932
if (join->tables > 1)
6933
cond->update_used_tables(); // Tablenr may have changed
6934
if (join->const_tables == join->tables &&
6935
session->lex->current_select->master_unit() ==
6936
&session->lex->unit) // not upper level SELECT
6937
join->const_table_map|=RAND_TABLE_BIT;
6938
{ // Check const tables
6940
make_cond_for_table(cond,
6941
join->const_table_map,
6943
for (JOIN_TAB *tab= join->join_tab+join->const_tables;
6944
tab < join->join_tab+join->tables ; tab++)
6946
if (*tab->on_expr_ref)
6948
JOIN_TAB *cond_tab= tab->first_inner;
6949
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
6950
join->const_table_map,
6954
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
6957
tmp->quick_fix_field();
6958
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
6959
new Item_cond_and(cond_tab->select_cond,
6961
if (!cond_tab->select_cond)
6963
cond_tab->select_cond->quick_fix_field();
6966
if (const_cond && !const_cond->val_int())
6968
return(1); // Impossible const condition
6972
used_tables=((select->const_tables=join->const_table_map) |
6973
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
6974
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6976
JOIN_TAB *tab=join->join_tab+i;
6978
first_inner is the X in queries like:
6979
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
6981
JOIN_TAB *first_inner_tab= tab->first_inner;
6982
table_map current_map= tab->table->map;
6983
bool use_quick_range=0;
6987
Following force including random expression in last table condition.
6988
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
6990
if (i == join->tables-1)
6991
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
6992
used_tables|=current_map;
6994
if (tab->type == JT_REF && tab->quick &&
6995
(uint32_t) tab->ref.key == tab->quick->index &&
6996
tab->ref.key_length < tab->quick->max_used_key_length)
6998
/* Range uses longer key; Use this instead of ref on key */
7003
tab->ref.key_parts=0; // Don't use ref key.
7004
join->best_positions[i].records_read= rows2double(tab->quick->records);
7006
We will use join cache here : prevent sorting of the first
7007
table only and sort at the end.
7009
if (i != join->const_tables && join->tables > join->const_tables + 1)
7015
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
7016
if (cond && !tmp && tab->quick)
7018
if (tab->type != JT_ALL)
7021
Don't use the quick method
7022
We come here in the case where we have 'key=constant' and
7023
the test is removed by make_cond_for_table()
7031
Hack to handle the case where we only refer to a table
7032
in the ON part of an OUTER JOIN. In this case we want the code
7033
below to check if we should use 'quick' instead.
7035
tmp= new Item_int((int64_t) 1,1); // Always true
7039
if (tmp || !cond || tab->type == JT_REF || tab->type == JT_REF_OR_NULL ||
7040
tab->type == JT_EQ_REF)
7042
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
7043
session->memdup((unsigned char*) select,
7046
return(1); // End of memory
7048
If tab is an inner table of an outer join operation,
7049
add a match guard to the pushed down predicate.
7050
The guard will turn the predicate on only after
7051
the first match for outer tables is encountered.
7056
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
7057
a cond, so neutralize the hack above.
7059
if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
7061
tab->select_cond=sel->cond=tmp;
7062
/* Push condition to storage engine if this is enabled
7063
and the condition is not guarded */
7064
tab->table->file->pushed_cond= NULL;
7065
if (session->variables.engine_condition_pushdown)
7068
make_cond_for_table(tmp, current_map, current_map, 0);
7071
/* Push condition to handler */
7072
if (!tab->table->file->cond_push(push_cond))
7073
tab->table->file->pushed_cond= push_cond;
7078
tab->select_cond= sel->cond= NULL;
7080
sel->head=tab->table;
7083
/* Use quick key read if it's a constant and it's not used
7085
if (tab->needed_reg.none() && tab->type != JT_EQ_REF
7086
&& (tab->type != JT_REF || (uint32_t) tab->ref.key == tab->quick->index))
7088
sel->quick=tab->quick; // Use value from get_quick_...
7089
sel->quick_keys.reset();
7090
sel->needed_reg.reset();
7098
uint32_t ref_key=(uint32_t) sel->head->reginfo.join_tab->ref.key+1;
7099
if (i == join->const_tables && ref_key)
7101
if (tab->const_keys.any() &&
7102
tab->table->reginfo.impossible_range)
7105
else if (tab->type == JT_ALL && ! use_quick_range)
7107
if (tab->const_keys.any() &&
7108
tab->table->reginfo.impossible_range)
7109
return(1); // Impossible range
7111
We plan to scan all rows.
7112
Check again if we should use an index.
7113
We could have used an column from a previous table in
7114
the index if we are using limit and this is the first table
7117
if ((cond && (!((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
7118
(!tab->const_keys.none() && (i == join->const_tables) && (join->unit->select_limit_cnt < join->best_positions[i].records_read) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
7120
/* Join with outer join condition */
7121
COND *orig_cond=sel->cond;
7122
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
7125
We can't call sel->cond->fix_fields,
7126
as it will break tab->on_expr if it's AND condition
7127
(fix_fields currently removes extra AND/OR levels).
7128
Yet attributes of the just built condition are not needed.
7129
Thus we call sel->cond->quick_fix_field for safety.
7131
if (sel->cond && !sel->cond->fixed)
7132
sel->cond->quick_fix_field();
7134
if (sel->test_quick_select(session, tab->keys,
7135
used_tables & ~ current_map,
7136
(join->select_options &
7139
join->unit->select_limit_cnt), 0,
7143
Before reporting "Impossible WHERE" for the whole query
7144
we have to check isn't it only "impossible ON" instead
7146
sel->cond=orig_cond;
7147
if (!*tab->on_expr_ref ||
7148
sel->test_quick_select(session, tab->keys,
7149
used_tables & ~ current_map,
7150
(join->select_options &
7153
join->unit->select_limit_cnt),0,
7155
return(1); // Impossible WHERE
7158
sel->cond=orig_cond;
7160
/* Fix for EXPLAIN */
7162
join->best_positions[i].records_read= (double)sel->quick->records;
7166
sel->needed_reg=tab->needed_reg;
7167
sel->quick_keys.reset();
7169
if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
7170
!((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
7172
tab->keys= sel->quick_keys;
7173
tab->keys|= sel->needed_reg;
7174
tab->use_quick= (!sel->needed_reg.none() &&
7175
(select->quick_keys.none() ||
7177
(select->quick->records >= 100L)))) ?
7179
sel->read_tables= used_tables & ~current_map;
7181
if (i != join->const_tables && tab->use_quick != 2)
7182
{ /* Read with cache */
7184
(tmp=make_cond_for_table(cond,
7185
join->const_table_map |
7189
tab->cache.select=(SQL_SELECT*)
7190
session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
7191
tab->cache.select->cond=tmp;
7192
tab->cache.select->read_tables=join->const_table_map;
7199
Push down conditions from all on expressions.
7200
Each of these conditions are guarded by a variable
7201
that turns if off just before null complemented row for
7202
outer joins is formed. Thus, the condition from an
7203
'on expression' are guaranteed not to be checked for
7204
the null complemented row.
7207
/* First push down constant conditions from on expressions */
7208
for (JOIN_TAB *join_tab= join->join_tab+join->const_tables;
7209
join_tab < join->join_tab+join->tables ; join_tab++)
7211
if (*join_tab->on_expr_ref)
7213
JOIN_TAB *cond_tab= join_tab->first_inner;
7214
tmp= make_cond_for_table(*join_tab->on_expr_ref,
7215
join->const_table_map,
7219
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
7222
tmp->quick_fix_field();
7223
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
7224
new Item_cond_and(cond_tab->select_cond,tmp);
7225
if (!cond_tab->select_cond)
7227
cond_tab->select_cond->quick_fix_field();
7231
/* Push down non-constant conditions from on expressions */
7232
JOIN_TAB *last_tab= tab;
7233
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
7236
Table tab is the last inner table of an outer join.
7237
An on expression is always attached to it.
7239
COND *on_expr= *first_inner_tab->on_expr_ref;
7241
table_map used_tables2= (join->const_table_map |
7242
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7243
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
7245
current_map= tab->table->map;
7246
used_tables2|= current_map;
7247
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
7251
JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
7253
First add the guards for match variables of
7254
all embedding outer join operations.
7256
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
7261
Now add the guard turning the predicate off for
7262
the null complemented row.
7264
tmp_cond= new Item_func_trig_cond(tmp_cond,
7268
tmp_cond->quick_fix_field();
7269
/* Add the predicate to other pushed down predicates */
7270
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
7271
new Item_cond_and(cond_tab->select_cond,
7273
if (!cond_tab->select_cond)
7275
cond_tab->select_cond->quick_fix_field();
7278
first_inner_tab= first_inner_tab->first_upper;
7287
2289
Check if given expression uses only table fields covered by the given index
9591
3886
if (!(left_const && right_const) &&
9592
3887
args[0]->result_type() == args[1]->result_type())
9596
resolve_const_item(session, &args[1], args[0]);
9597
func->update_used_tables();
9598
change_cond_ref_to_const(session, save_list, and_father, and_father,
9601
else if (left_const)
9603
resolve_const_item(session, &args[0], args[1]);
9604
func->update_used_tables();
9605
change_cond_ref_to_const(session, save_list, and_father, and_father,
9615
Simplify joins replacing outer joins by inner joins whenever it's
9618
The function, during a retrieval of join_list, eliminates those
9619
outer joins that can be converted into inner join, possibly nested.
9620
It also moves the on expressions for the converted outer joins
9621
and from inner joins to conds.
9622
The function also calculates some attributes for nested joins:
9626
- on_expr_dep_tables
9627
The first two attributes are used to test whether an outer join can
9628
be substituted for an inner join. The third attribute represents the
9629
relation 'to be dependent on' for tables. If table t2 is dependent
9630
on table t1, then in any evaluated execution plan table access to
9631
table t2 must precede access to table t2. This relation is used also
9632
to check whether the query contains invalid cross-references.
9633
The forth attribute is an auxiliary one and is used to calculate
9635
As the attribute dep_tables qualifies possibles orders of tables in the
9636
execution plan, the dependencies required by the straight join
9637
modifiers are reflected in this attribute as well.
9638
The function also removes all braces that can be removed from the join
9639
expression without changing its meaning.
9642
An outer join can be replaced by an inner join if the where condition
9643
or the on expression for an embedding nested join contains a conjunctive
9644
predicate rejecting null values for some attribute of the inner tables.
9648
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9650
the predicate t2.b < 5 rejects nulls.
9651
The query is converted first to:
9653
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9655
then to the equivalent form:
9657
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
9661
Similarly the following query:
9663
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
9668
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
9672
One conversion might trigger another:
9674
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
9675
LEFT JOIN t3 ON t3.b=t2.b
9676
WHERE t3 IS NOT NULL =>
9677
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
9678
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
9679
SELECT * FROM t1, t2, t3
9680
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
9683
The function removes all unnecessary braces from the expression
9684
produced by the conversions.
9687
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9689
finally is converted to:
9691
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9696
It also will remove braces from the following queries:
9698
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
9699
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
9702
The benefit of this simplification procedure is that it might return
9703
a query for which the optimizer can evaluate execution plan with more
9704
join orders. With a left join operation the optimizer does not
9705
consider any plan where one of the inner tables is before some of outer
9709
The function is implemented by a recursive procedure. On the recursive
9710
ascent all attributes are calculated, all outer joins that can be
9711
converted are replaced and then all unnecessary braces are removed.
9712
As join list contains join tables in the reverse order sequential
9713
elimination of outer joins does not require extra recursive calls.
9716
Remove all semi-joins that have are within another semi-join (i.e. have
9717
an "ancestor" semi-join nest)
9720
Here is an example of a join query with invalid cross references:
9722
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
9725
@param join reference to the query info
9726
@param join_list list representation of the join to be converted
9727
@param conds conditions to add on expressions for converted joins
9728
@param top true <=> conds is the where condition
9731
- The new condition, if success
9736
simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top,
9740
nested_join_st *nested_join;
9741
TableList *prev_table= 0;
9742
List_iterator<TableList> li(*join_list);
9745
Try to simplify join operations from join_list.
9746
The most outer join operation is checked for conversion first.
9748
while ((table= li++))
9750
table_map used_tables;
9751
table_map not_null_tables= (table_map) 0;
9753
if ((nested_join= table->nested_join))
9756
If the element of join_list is a nested join apply
9757
the procedure to its nested join list first.
9761
Item *expr= table->on_expr;
9763
If an on expression E is attached to the table,
9764
check all null rejected predicates in this expression.
9765
If such a predicate over an attribute belonging to
9766
an inner table of an embedded outer join is found,
9767
the outer join is converted to an inner join and
9768
the corresponding on expression is added to E.
9770
expr= simplify_joins(join, &nested_join->join_list,
9771
expr, false, in_sj || table->sj_on_expr);
9773
if (!table->prep_on_expr || expr != table->on_expr)
9777
table->on_expr= expr;
9778
table->prep_on_expr= expr->copy_andor_structure(join->session);
9781
nested_join->used_tables= (table_map) 0;
9782
nested_join->not_null_tables=(table_map) 0;
9783
conds= simplify_joins(join, &nested_join->join_list, conds, top,
9784
in_sj || table->sj_on_expr);
9785
used_tables= nested_join->used_tables;
9786
not_null_tables= nested_join->not_null_tables;
9790
if (!table->prep_on_expr)
9791
table->prep_on_expr= table->on_expr;
9792
used_tables= table->table->map;
9794
not_null_tables= conds->not_null_tables();
9797
if (table->embedding)
9799
table->embedding->nested_join->used_tables|= used_tables;
9800
table->embedding->nested_join->not_null_tables|= not_null_tables;
9803
if (!table->outer_join || (used_tables & not_null_tables))
9806
For some of the inner tables there are conjunctive predicates
9807
that reject nulls => the outer join can be replaced by an inner join.
9809
table->outer_join= 0;
9812
/* Add ON expression to the WHERE or upper-level ON condition. */
9815
conds= and_conds(conds, table->on_expr);
9816
conds->top_level_item();
9817
/* conds is always a new item as both cond and on_expr existed */
9818
assert(!conds->fixed);
9819
conds->fix_fields(join->session, &conds);
9822
conds= table->on_expr;
9823
table->prep_on_expr= table->on_expr= 0;
9831
Only inner tables of non-convertible outer joins
9832
remain with on_expr.
9836
table->dep_tables|= table->on_expr->used_tables();
9837
if (table->embedding)
9839
table->dep_tables&= ~table->embedding->nested_join->used_tables;
9841
Embedding table depends on tables used
9842
in embedded on expressions.
9844
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
9847
table->dep_tables&= ~table->table->map;
9852
/* The order of tables is reverse: prev_table follows table */
9853
if (prev_table->straight)
9854
prev_table->dep_tables|= used_tables;
9855
if (prev_table->on_expr)
9857
prev_table->dep_tables|= table->on_expr_dep_tables;
9858
table_map prev_used_tables= prev_table->nested_join ?
9859
prev_table->nested_join->used_tables :
9860
prev_table->table->map;
9862
If on expression contains only references to inner tables
9863
we still make the inner tables dependent on the outer tables.
9864
It would be enough to set dependency only on one outer table
9865
for them. Yet this is really a rare case.
9867
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
9868
prev_table->dep_tables|= used_tables;
9875
Flatten nested joins that can be flattened.
9876
no ON expression and not a semi-join => can be flattened.
9879
while ((table= li++))
9881
nested_join= table->nested_join;
9882
if (table->sj_on_expr && !in_sj)
9885
If this is a semi-join that is not contained within another semi-join,
9886
leave it intact (otherwise it is flattened)
9888
join->select_lex->sj_nests.push_back(table);
9890
else if (nested_join && !table->on_expr)
9893
List_iterator<TableList> it(nested_join->join_list);
9896
tbl->embedding= table->embedding;
9897
tbl->join_list= table->join_list;
9899
li.replace(nested_join->join_list);
9907
Assign each nested join structure a bit in nested_join_map.
9909
Assign each nested join structure (except "confluent" ones - those that
9910
embed only one element) a bit in nested_join_map.
9912
@param join Join being processed
9913
@param join_list List of tables
9914
@param first_unused Number of first unused bit in nested_join_map before the
9918
This function is called after simplify_joins(), when there are no
9919
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
9920
we will not run out of bits in nested_join_map.
9923
First unused bit in nested_join_map after the call.
9926
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
9927
uint32_t first_unused)
9929
List_iterator<TableList> li(*join_list);
9931
while ((table= li++))
9933
nested_join_st *nested_join;
9934
if ((nested_join= table->nested_join))
9937
It is guaranteed by simplify_joins() function that a nested join
9938
that has only one child is either
9939
- a single-table view (the child is the underlying table), or
9940
- a single-table semi-join nest
9942
We don't assign bits to such sj-nests because
9943
1. it is redundant (a "sequence" of one table cannot be interleaved
9945
2. we could run out bits in nested_join_map otherwise.
9947
if (nested_join->join_list.elements != 1)
9949
/* Don't assign bits to sj-nests */
9951
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
9952
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
9957
return(first_unused);
9962
Set nested_join_st::counter=0 in all nested joins in passed list.
9964
Recursively set nested_join_st::counter=0 for all nested joins contained in
9965
the passed join_list.
9967
@param join_list List of nested joins to process. It may also contain base
9968
tables which will be ignored.
9971
static void reset_nj_counters(List<TableList> *join_list)
9973
List_iterator<TableList> li(*join_list);
9975
while ((table= li++))
9977
nested_join_st *nested_join;
9978
if ((nested_join= table->nested_join))
9980
nested_join->counter_= 0;
9981
reset_nj_counters(&nested_join->join_list);
3891
resolve_const_item(session, &args[1], args[0]);
3892
func->update_used_tables();
3893
change_cond_ref_to_const(session, save_list, and_father, and_father,
3896
else if (left_const)
3898
resolve_const_item(session, &args[0], args[1]);
3899
func->update_used_tables();
3900
change_cond_ref_to_const(session, save_list, and_father, and_father,
9989
3909
Check interleaving with an inner tables of an outer join for