20
20
mysql_select and join optimization
22
23
@defgroup Query_Optimizer Query Optimizer
32
#include "drizzled/sql_select.h" /* include join.h */
34
#include "drizzled/error.h"
35
#include "drizzled/gettext.h"
36
#include "drizzled/util/test.h"
37
#include "drizzled/name_resolution_context_state.h"
38
#include "drizzled/nested_join.h"
39
#include "drizzled/probes.h"
40
#include "drizzled/show.h"
41
#include "drizzled/item/cache.h"
42
#include "drizzled/item/cmpfunc.h"
43
#include "drizzled/item/copy_string.h"
44
#include "drizzled/item/uint.h"
45
#include "drizzled/cached_item.h"
46
#include "drizzled/sql_base.h"
47
#include "drizzled/field/blob.h"
48
#include "drizzled/check_stack_overrun.h"
49
#include "drizzled/lock.h"
50
#include "drizzled/item/outer_ref.h"
51
#include "drizzled/index_hint.h"
52
#include "drizzled/records.h"
53
#include "drizzled/internal/iocache.h"
54
#include "drizzled/drizzled.h"
56
#include "drizzled/sql_union.h"
57
#include "drizzled/optimizer/key_field.h"
58
#include "drizzled/optimizer/position.h"
59
#include "drizzled/optimizer/sargable_param.h"
60
#include "drizzled/optimizer/key_use.h"
61
#include "drizzled/optimizer/range.h"
62
#include "drizzled/optimizer/quick_range_select.h"
63
#include "drizzled/optimizer/quick_ror_intersect_select.h"
65
#include "drizzled/filesort.h"
72
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);
73
static COND *build_equal_items(Session *session, COND *cond,
26
#include <drizzled/server_includes.h>
27
#include <drizzled/sql_select.h>
28
#include "sj_tmp_table.h"
30
#include <mysys/my_bit.h>
31
#include <drizzled/drizzled_error_messages.h>
32
#include <libdrizzle/gettext.h>
33
#include <drizzled/util/test.h>
35
const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
36
"MAYBE_REF","ALL","range","index",
37
"ref_or_null","unique_subquery","index_subquery",
41
struct st_sargable_param;
43
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
44
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds,
45
DYNAMIC_ARRAY *keyuse);
46
static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,
48
uint32_t tables, COND *conds,
49
COND_EQUAL *cond_equal,
50
table_map table_map, SELECT_LEX *select_lex,
51
st_sargable_param **sargables);
52
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
53
static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);
54
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
55
table_map used_tables);
56
static bool choose_plan(JOIN *join,table_map join_tables);
58
static void best_access_path(JOIN *join, JOIN_TAB *s, THD *thd,
59
table_map remaining_tables, uint32_t idx,
60
double record_count, double read_time);
61
static void optimize_straight_join(JOIN *join, table_map join_tables);
62
static bool greedy_search(JOIN *join, table_map remaining_tables,
63
uint32_t depth, uint32_t prune_level);
64
static bool best_extension_by_limited_search(JOIN *join,
65
table_map remaining_tables,
66
uint32_t idx, double record_count,
67
double read_time, uint32_t depth,
68
uint32_t prune_level);
69
static uint32_t determine_search_depth(JOIN* join);
70
static int join_tab_cmp(const void* ptr1, const void* ptr2);
71
static int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
73
TODO: 'find_best' is here only temporarily until 'greedy_search' is
76
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index,
77
double record_count,double read_time);
78
static uint32_t cache_record_length(JOIN *join,uint32_t index);
79
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
80
static bool get_best_combination(JOIN *join);
81
static store_key *get_store_key(THD *thd,
82
KEYUSE *keyuse, table_map used_tables,
83
KEY_PART_INFO *key_part, unsigned char *key_buff,
85
static bool make_simple_join(JOIN *join,Table *tmp_table);
86
static void make_outerjoin_info(JOIN *join);
87
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
88
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
89
static bool only_eq_ref_tables(JOIN *join, order_st *order, table_map tables);
90
static void update_depend_map(JOIN *join);
91
static void update_depend_map(JOIN *join, order_st *order);
92
static order_st *remove_const(JOIN *join,order_st *first_order,COND *cond,
93
bool change_list, bool *simple_order);
94
static int return_zero_rows(JOIN *join, select_result *res,TableList *tables,
95
List<Item> &fields, bool send_row,
96
uint64_t select_options, const char *info,
98
static COND *build_equal_items(THD *thd, COND *cond,
74
99
COND_EQUAL *inherited,
75
100
List<TableList> *join_list,
76
101
COND_EQUAL **cond_equal_ref);
102
static COND* substitute_for_best_equal_field(COND *cond,
103
COND_EQUAL *cond_equal,
104
void *table_join_idx);
105
static COND *simplify_joins(JOIN *join, List<TableList> *join_list,
106
COND *conds, bool top, bool in_sj);
107
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
108
static void restore_prev_nj_state(JOIN_TAB *last);
109
static void reset_nj_counters(List<TableList> *join_list);
110
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
111
uint32_t first_unused);
114
void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);
115
static void restore_prev_sj_state(const table_map remaining_tables,
116
const JOIN_TAB *tab);
118
static COND *optimize_cond(JOIN *join, COND *conds,
119
List<TableList> *join_list,
120
Item::cond_result *cond_value);
121
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
122
static int do_select(JOIN *join,List<Item> *fields,Table *tmp_table);
124
static enum_nested_loop_state
125
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
127
static enum_nested_loop_state
128
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
129
static enum_nested_loop_state
130
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
131
static enum_nested_loop_state
132
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
133
static enum_nested_loop_state
134
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
135
static enum_nested_loop_state
136
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
137
static enum_nested_loop_state
138
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
140
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
141
static int join_read_system(JOIN_TAB *tab);
142
static int join_read_const(JOIN_TAB *tab);
143
static int join_read_key(JOIN_TAB *tab);
144
static int join_read_always_key(JOIN_TAB *tab);
145
static int join_read_last_key(JOIN_TAB *tab);
146
static int join_no_more_records(READ_RECORD *info);
147
static int join_read_next(READ_RECORD *info);
148
static int join_read_next_different(READ_RECORD *info);
149
static int join_init_quick_read_record(JOIN_TAB *tab);
150
static int test_if_quick_select(JOIN_TAB *tab);
151
static int join_init_read_record(JOIN_TAB *tab);
152
static int join_read_first(JOIN_TAB *tab);
153
static int join_read_next_same(READ_RECORD *info);
154
static int join_read_next_same_diff(READ_RECORD *info);
155
static int join_read_last(JOIN_TAB *tab);
156
static int join_read_prev_same(READ_RECORD *info);
157
static int join_read_prev(READ_RECORD *info);
158
int join_read_always_key_or_null(JOIN_TAB *tab);
159
int join_read_next_same_or_null(READ_RECORD *info);
160
static COND *make_cond_for_table(COND *cond,table_map table,
161
table_map used_table,
162
bool exclude_expensive_cond);
78
163
static Item* part_of_refkey(Table *form,Field *field);
79
static bool cmp_buffer_with_ref(JoinTable *tab);
80
static void change_cond_ref_to_const(Session *session,
81
vector<COND_CMP>& save_list,
86
static bool copy_blobs(Field **ptr);
164
static bool test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,
165
ha_rows select_limit, bool no_changes,
167
static bool list_contains_unique_index(Table *table,
168
bool (*find_func) (Field *, void *), void *data);
169
static bool find_field_in_item_list (Field *field, void *data);
170
static bool find_field_in_order_list (Field *field, void *data);
171
static int create_sort_index(THD *thd, JOIN *join, order_st *order,
172
ha_rows filesort_limit, ha_rows select_limit,
174
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields,
176
static int remove_dup_with_compare(THD *thd, Table *entry, Field **field,
177
ulong offset,Item *having);
178
static int remove_dup_with_hash_index(THD *thd,Table *table,
179
uint32_t field_count, Field **first_field,
88
static bool eval_const_cond(COND *cond)
90
return ((Item_func*) cond)->val_int() ? true : false;
181
ulong key_length,Item *having);
182
static int join_init_cache(THD *thd,JOIN_TAB *tables,uint32_t table_count);
183
static ulong used_blob_length(CACHE_FIELD **ptr);
184
static bool store_record_in_cache(JOIN_CACHE *cache);
185
static void reset_cache_read(JOIN_CACHE *cache);
186
static void reset_cache_write(JOIN_CACHE *cache);
187
static void read_cached_record(JOIN_TAB *tab);
188
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
189
static order_st *create_distinct_group(THD *thd, Item **ref_pointer_array,
190
order_st *order, List<Item> &fields,
191
List<Item> &all_fields,
192
bool *all_order_by_fields_used);
193
static bool test_if_subpart(order_st *a,order_st *b);
194
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
195
static void calc_group_buffer(JOIN *join,order_st *group);
196
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
197
static bool alloc_group_fields(JOIN *join,order_st *group);
198
// Create list for using with tempory table
199
static bool change_to_use_tmp_fields(THD *thd, Item **ref_pointer_array,
200
List<Item> &new_list1,
201
List<Item> &new_list2,
202
uint32_t elements, List<Item> &items);
203
// Create list for using with tempory table
204
static bool change_refs_to_tmp_fields(THD *thd, Item **ref_pointer_array,
205
List<Item> &new_list1,
206
List<Item> &new_list2,
207
uint32_t elements, List<Item> &items);
208
static void init_tmptable_sum_functions(Item_sum **func);
209
static void update_tmptable_sum_func(Item_sum **func,Table *tmp_table);
210
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
211
static bool add_ref_to_table_cond(THD *thd, JOIN_TAB *join_tab);
212
static bool setup_sum_funcs(THD *thd, Item_sum **func_ptr);
213
static bool init_sum_functions(Item_sum **func, Item_sum **end);
214
static bool update_sum_func(Item_sum **func);
215
void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
216
bool distinct, const char *message=NULL);
217
static Item *remove_additional_cond(Item* conds);
218
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
219
static bool test_if_ref(Item_field *left_item,Item *right_item);
220
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
221
Item *new_cond, bool fix_fields);
94
224
This is used to mark equalities that were made from i-th IN-equality.
259
383
ref->outer_ref= new_ref;
260
384
ref->ref= &ref->outer_ref;
262
if (!ref->fixed && ref->fix_fields(session, 0))
386
if (!ref->fixed && ref->fix_fields(thd, 0))
264
session->used_tables|= item->used_tables();
388
thd->used_tables|= item->used_tables();
393
#define MAGIC_IN_WHERE_TOP_LEVEL 10
395
Function to setup clauses without sum functions.
397
inline int setup_without_group(THD *thd, Item **ref_pointer_array,
401
List<Item> &all_fields,
404
order_st *group, bool *hidden_group_fields)
407
nesting_map save_allow_sum_func=thd->lex->allow_sum_func ;
409
thd->lex->allow_sum_func&= ~(1 << thd->lex->current_select->nest_level);
410
res= setup_conds(thd, tables, leaves, conds);
412
thd->lex->allow_sum_func|= 1 << thd->lex->current_select->nest_level;
413
res= res || setup_order(thd, ref_pointer_array, tables, fields, all_fields,
415
thd->lex->allow_sum_func&= ~(1 << thd->lex->current_select->nest_level);
416
res= res || setup_group(thd, ref_pointer_array, tables, fields, all_fields,
417
group, hidden_group_fields);
418
thd->lex->allow_sum_func= save_allow_sum_func;
269
422
/*****************************************************************************
270
423
Check fields, find best join, do the select and output fields.
271
424
mysql_select assumes that all tables are already opened
272
425
*****************************************************************************/
428
Prepare of whole select (including sub queries in future).
431
Add check of calculation of GROUP functions and fields:
432
SELECT COUNT(*)+table.col1 from table1;
440
JOIN::prepare(Item ***rref_pointer_array,
441
TableList *tables_init,
442
uint32_t wild_num, COND *conds_init, uint32_t og_num,
443
order_st *order_init, order_st *group_init,
445
order_st *proc_param_init, SELECT_LEX *select_lex_arg,
446
SELECT_LEX_UNIT *unit_arg)
448
// to prevent double initialization on EXPLAIN
454
group_list= group_init;
456
proc_param= proc_param_init;
457
tables_list= tables_init;
458
select_lex= select_lex_arg;
459
select_lex->join= this;
460
join_list= &select_lex->top_join_list;
461
union_part= unit_arg->is_union();
463
thd->lex->current_select->is_item_list_lookup= 1;
465
If we have already executed SELECT, then it have not sense to prevent
466
its table from update (see unique_table())
468
if (thd->derived_tables_processing)
469
select_lex->exclude_from_table_unique_test= true;
471
/* Check that all tables, fields, conds and order are ok */
473
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
474
setup_tables_and_check_access(thd, &select_lex->context, join_list,
475
tables_list, &select_lex->leaf_tables,
479
TableList *table_ptr;
480
for (table_ptr= select_lex->leaf_tables;
482
table_ptr= table_ptr->next_leaf)
485
if (setup_wild(thd, tables_list, fields_list, &all_fields, wild_num) ||
486
select_lex->setup_ref_array(thd, og_num) ||
487
setup_fields(thd, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
489
setup_without_group(thd, (*rref_pointer_array), tables_list,
490
select_lex->leaf_tables, fields_list,
491
all_fields, &conds, order, group_list,
492
&hidden_group_fields))
493
return(-1); /* purecov: inspected */
495
ref_pointer_array= *rref_pointer_array;
499
nesting_map save_allow_sum_func= thd->lex->allow_sum_func;
500
thd->where="having clause";
501
thd->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
502
select_lex->having_fix_field= 1;
503
bool having_fix_rc= (!having->fixed &&
504
(having->fix_fields(thd, &having) ||
505
having->check_cols(1)));
506
select_lex->having_fix_field= 0;
507
if (having_fix_rc || thd->is_error())
508
return(-1); /* purecov: inspected */
509
thd->lex->allow_sum_func= save_allow_sum_func;
513
Item_subselect *subselect;
514
Item_in_subselect *in_subs= NULL;
516
Are we in a subquery predicate?
517
TODO: the block below will be executed for every PS execution without need.
519
if ((subselect= select_lex->master_unit()->item))
521
bool do_semijoin= !test(thd->variables.optimizer_switch &
522
OPTIMIZER_SWITCH_NO_SEMIJOIN);
523
if (subselect->substype() == Item_subselect::IN_SUBS)
524
in_subs= (Item_in_subselect*)subselect;
527
Check if we're in subquery that is a candidate for flattening into a
528
semi-join (which is done done in flatten_subqueries()). The
530
1. Subquery predicate is an IN/=ANY subq predicate
531
2. Subquery is a single SELECT (not a UNION)
532
3. Subquery does not have GROUP BY or order_st BY
533
4. Subquery does not use aggregate functions or HAVING
534
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
535
6. No execution method was already chosen (by a prepared statement).
537
(*). We are not in a subquery of a single table UPDATE/DELETE that
538
doesn't have a JOIN (TODO: We should handle this at some
539
point by switching to multi-table UPDATE/DELETE)
541
(**). We're not in a confluent table-less subquery, like
545
!select_lex->master_unit()->first_select()->next_select() && // 2
546
!select_lex->group_list.elements && !order && // 3
547
!having && !select_lex->with_sum_func && // 4
548
thd->thd_marker && // 5
549
select_lex->outer_select()->join && // (*)
550
select_lex->master_unit()->first_select()->leaf_tables && // (**)
552
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
555
if (!in_subs->left_expr->fixed &&
556
in_subs->left_expr->fix_fields(thd, &in_subs->left_expr))
561
Check that the right part of the subselect contains no more than one
562
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
564
if (subselect->substype() == Item_subselect::IN_SUBS &&
565
(select_lex->item_list.elements !=
566
((Item_in_subselect*)subselect)->left_expr->cols()))
568
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
573
/* Register the subquery for further processing */
574
select_lex->outer_select()->join->sj_subselects.append(thd->mem_root, in_subs);
575
in_subs->expr_join_nest= (TableList*)thd->thd_marker;
579
bool do_materialize= !test(thd->variables.optimizer_switch &
580
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
582
Check if the subquery predicate can be executed via materialization.
583
The required conditions are:
584
1. Subquery predicate is an IN/=ANY subq predicate
585
2. Subquery is a single SELECT (not a UNION)
586
3. Subquery is not a table-less query. In this case there is no
587
point in materializing.
588
4. Subquery predicate is a top-level predicate
589
(this implies it is not negated)
590
TODO: this is a limitation that should be lifeted once we
591
implement correct NULL semantics (WL#3830)
592
5. Subquery is non-correlated
594
This is an overly restrictive condition. It can be extended to:
595
(Subquery is non-correlated ||
596
Subquery is correlated to any query outer to IN predicate ||
597
(Subquery is correlated to the immediate outer query &&
598
Subquery !contains {GROUP BY, order_st BY [LIMIT],
599
aggregate functions) && subquery predicate is not under "NOT IN"))
600
6. No execution method was already chosen (by a prepared statement).
602
(*) The subquery must be part of a SELECT statement. The current
603
condition also excludes multi-table update statements.
605
We have to determine whether we will perform subquery materialization
606
before calling the IN=>EXISTS transformation, so that we know whether to
607
perform the whole transformation or only that part of it which wraps
608
Item_in_subselect in an Item_in_optimizer.
610
if (do_materialize &&
612
!select_lex->master_unit()->first_select()->next_select() && // 2
613
select_lex->master_unit()->first_select()->leaf_tables && // 3
614
thd->lex->sql_command == SQLCOM_SELECT) // *
616
if (in_subs->is_top_level_item() && // 4
617
!in_subs->is_correlated && // 5
618
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
619
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
622
Item_subselect::trans_res trans_res;
623
if ((trans_res= subselect->select_transformer(this)) !=
624
Item_subselect::RES_OK)
626
return((trans_res == Item_subselect::RES_ERROR));
635
for (ord= order; ord; ord= ord->next)
637
Item *item= *ord->item;
638
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
639
item->split_sum_func(thd, ref_pointer_array, all_fields);
643
if (having && having->with_sum_func)
644
having->split_sum_func2(thd, ref_pointer_array, all_fields,
646
if (select_lex->inner_sum_func_list)
648
Item_sum *end=select_lex->inner_sum_func_list;
649
Item_sum *item_sum= end;
652
item_sum= item_sum->next;
653
item_sum->split_sum_func2(thd, ref_pointer_array,
654
all_fields, item_sum->ref_by, false);
655
} while (item_sum != end);
658
if (select_lex->inner_refs_list.elements &&
659
fix_inner_refs(thd, all_fields, select_lex, ref_pointer_array))
663
Check if there are references to un-aggregated columns when computing
664
aggregate functions with implicit grouping (there is no GROUP BY).
666
MODE_ONLY_FULL_GROUP_BY is enabled here by default
668
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
670
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
671
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
675
/* Caclulate the number of groups */
677
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
682
goto err; /* purecov: inspected */
684
if (result && result->prepare(fields_list, unit_arg))
685
goto err; /* purecov: inspected */
687
/* Init join struct */
688
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
689
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
690
this->group= group_list != 0;
693
#ifdef RESTRICTED_GROUP
694
if (sum_func_count && !group_list && (func_count || field_count))
696
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
700
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
702
if (alloc_func_list())
708
return(-1); /* purecov: inspected */
713
Remove the predicates pushed down into the subquery
716
JOIN::remove_subq_pushed_predicates()
717
where IN Must be NULL
718
OUT The remaining WHERE condition, or NULL
721
Given that this join will be executed using (unique|index)_subquery,
722
without "checking NULL", remove the predicates that were pushed down
725
If the subquery compares scalar values, we can remove the condition that
726
was wrapped into trig_cond (it will be checked when needed by the subquery
729
If the subquery compares row values, we need to keep the wrapped
730
equalities in the WHERE clause: when the left (outer) tuple has both NULL
731
and non-NULL values, we'll do a full table scan and will rely on the
732
equalities corresponding to non-NULL parts of left tuple to filter out
733
non-matching records.
735
TODO: We can remove the equalities that will be guaranteed to be true by the
736
fact that subquery engine will be using index lookup. This must be done only
737
for cases where there are no conversion errors of significance, e.g. 257
738
that is searched in a byte. But this requires homogenization of the return
739
codes of all Field*::store() methods.
742
void JOIN::remove_subq_pushed_predicates(Item **where)
744
if (conds->type() == Item::FUNC_ITEM &&
745
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
746
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
747
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
748
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
749
((Item_func *)conds)->arguments()[0]))
275
758
Index lookup-based subquery: save some flags for EXPLAIN output
797
Check if the table's rowid is included in the temptable
800
sj_table_is_included()
802
join_tab The table to be checked
805
SemiJoinDuplicateElimination: check the table's rowid should be included
806
in the temptable. This is so if
808
1. The table is not embedded within some semi-join nest
809
2. The has been pulled out of a semi-join nest, or
811
3. The table is functionally dependent on some previous table
813
[4. This is also true for constant tables that can't be
814
NULL-complemented but this function is not called for such tables]
817
true - Include table's rowid
821
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
823
if (join_tab->emb_sj_nest)
826
/* Check if this table is functionally dependent on the tables that
827
are within the same outer join nest
829
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
830
if (join_tab->type == JT_EQ_REF)
832
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
834
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
836
JOIN_TAB *ref_tab= join->join_tab + idx;
837
if (embedding == ref_tab->table->pos_in_table_list->embedding)
840
/* Ok, functionally dependent */
843
/* Not functionally dependent => need to include*/
849
Setup the strategies to eliminate semi-join duplicates.
852
setup_semijoin_dups_elimination()
854
options Join options (needed to see if join buffering will be
856
no_jbuf_after Another bit of information re where join buffering will
860
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
863
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
865
2. FirstMatch (pick only the 1st matching row combination of inner tables)
866
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
867
together and picking the 1st one)
869
The join order has "duplicate-generating ranges", and every range is
870
served by one strategy or a combination of FirstMatch with with some
873
"Duplicate-generating range" is defined as a range within the join order
874
that contains all of the inner tables of a semi-join. All ranges must be
875
disjoint, if tables of several semi-joins are interleaved, then the ranges
876
are joined together, which is equivalent to converting
877
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
879
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
882
Applicability conditions are as follows:
884
DuplicateWeedout strategy
885
~~~~~~~~~~~~~~~~~~~~~~~~~
887
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
888
+------+ +=========================+ +---+
891
(1) - Prefix of OuterTables (those that participate in
892
IN-equality and/or are correlated with subquery) and outer
893
Noncorrelated Tables.
894
(2) - The handled range. The range starts with the first sj-inner
895
table, and covers all sj-inner and outer tables
896
Within the range, Inner, Outer, outer Noncorrelated tables
897
may follow in any order.
898
(3) - The suffix of outer Noncorrelated tables.
903
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
904
+------+ +==================+ +---+
907
(1) - Prefix of outer and non-correlated tables
908
(2) - The handled range, which may contain only inner and
909
non-correlated tables.
910
(3) - The suffix of outer Noncorrelated tables.
915
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
916
+--------+ +===========+ +=============+ +------+
919
(1) - Prefix that may contain any outer tables. The prefix must contain
920
all the non-trivially correlated outer tables. (non-trivially means
921
that the correlation is not just through the IN-equality).
923
(2) - Inner table for which the InsideOut scan is performed.
925
(3) - The remainder of the duplicate-generating range. It is served by
926
application of FirstMatch strategy, with the exception that
927
outer IN-correlated tables are considered to be non-correlated.
929
(4) - THe suffix of outer and outer non-correlated tables.
931
If several strategies are applicable, their relative priorities are:
936
This function walks over the join order and sets up the strategies by
937
setting appropriate members in join_tab structures.
941
true Out of memory error
945
int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
947
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
950
0 - invalid (EOF marker),
952
2 - Temptable (maybe confluent),
953
3 - Temptable with join buffering
956
uint32_t start_idx; /* Left range bound */
957
uint32_t end_idx; /* Right range bound */
959
For Temptable strategy: Bitmap of all outer and correlated tables from
960
all involved join nests.
962
table_map outer_tables;
963
} dups_ranges [MAX_TABLES];
965
TableList *emb_insideout_nest= NULL;
966
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
967
tables) whose ranges we're in */
968
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
969
table_map range_start_map= 0; /* table_map at current range start */
970
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
975
First pass: locate the duplicate-generating ranges and pick the strategies.
977
for (i=join->const_tables ; i < join->tables ; i++)
979
JOIN_TAB *tab=join->join_tab+i;
980
Table *table=tab->table;
981
cur_map |= table->map;
983
if (tab->emb_sj_nest) // Encountered an sj-inner table
987
dups_ranges[cur_range].start_idx= i;
988
range_start_map= cur_map & ~table->map;
990
Remember if this is a possible start of range that is covered by
991
the InsideOut strategy (the reason that it is not covered could
992
be that it overlaps with anther semi-join's range. we don't
993
support InsideOut for joined ranges)
995
if (join->best_positions[i].use_insideout_scan)
996
emb_insideout_nest= tab->emb_sj_nest;
999
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
1000
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
1002
if (tab->emb_sj_nest != emb_insideout_nest)
1005
Two different semi-joins interleave. This cannot be handled by
1008
emb_insideout_nest= NULL;
1012
if (emb_sj_map) /* We're in duplicate-generating range */
1014
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
1015
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
1016
i <= no_jbuf_after && !dealing_with_jbuf)
1019
This table uses join buffering, which makes use of FirstMatch or
1020
InsideOut strategies impossible for the current and (we assume)
1021
preceding duplicate-producing ranges.
1022
That is, for the join order:
1024
x x [ x x] x [x x x] x [x x X* x] x
1026
+-----+ +-----+ | join buffering use
1029
we'll have to remove r1 and r2 and use duplicate-elimination
1030
strategy that spans all the tables, starting from the very 1st
1033
dealing_with_jbuf= true;
1034
emb_insideout_nest= false;
1037
Absorb all preceding duplicate-eliminating ranges. Their strategies
1040
for (int prev_range= 0; prev_range < cur_range; prev_range++)
1042
dups_ranges[cur_range].outer_tables |=
1043
dups_ranges[prev_range].outer_tables;
1045
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
1046
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
1051
Check if we are at the end of duplicate-producing range. We are if
1053
1. It's an InsideOut range (which presumes all correlated tables are
1054
in the prefix), and all inner tables are in the join order prefix,
1056
2. It's a DuplicateElimination range (possibly covering several
1057
SJ-nests), and all inner, outer, and correlated tables of all
1058
sj-nests are in the join order prefix.
1060
bool end_of_range= false;
1061
if (emb_insideout_nest &&
1062
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
1064
/* Save that this range is handled with InsideOut: */
1065
dups_ranges[cur_range].strategy= 1;
1068
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
1071
This is a complete range to be handled with either DuplicateWeedout
1074
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
1076
This will hold tables from within the range that need to be put
1077
into the join buffer before we can use the FirstMatch on its tail.
1079
dups_ranges[cur_range].outer_tables= emb_outer_tables &
1086
dups_ranges[cur_range].end_idx= i+1;
1087
emb_sj_map= emb_outer_tables= 0;
1088
emb_insideout_nest= NULL;
1089
dealing_with_jbuf= false;
1090
dups_ranges[++cur_range].strategy= 0;
1095
THD *thd= join->thd;
1096
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
1098
Second pass: setup the chosen strategies
1100
for (int j= 0; j < cur_range; j++)
1102
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
1104
if (dups_ranges[j].strategy == 1) // InsideOut strategy
1106
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
1109
else // DuplicateWeedout strategy
1111
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
1112
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
1113
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
1114
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
1115
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
1116
uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
1117
JOIN_TAB *last_outer_tab= tab - 1;
1119
Walk through the range and remember
1120
- tables that need their rowids to be put into temptable
1121
- the last outer table
1123
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1125
if (sj_table_is_included(join, tab))
1127
last_tab->join_tab= tab;
1128
last_tab->rowid_offset= jt_rowid_offset;
1129
jt_rowid_offset += tab->table->file->ref_length;
1130
if (tab->table->maybe_null)
1132
last_tab->null_byte= jt_null_bits / 8;
1133
last_tab->null_bit= jt_null_bits++;
1136
tab->table->prepare_for_position();
1137
tab->rowid_keep_flags= rowid_keep_flags;
1139
cur_map |= tab->table->map;
1140
if (!tab->emb_sj_nest && bitmap_covers(cur_map,
1141
dups_ranges[j].outer_tables))
1142
last_outer_tab= tab;
1145
if (jt_rowid_offset) /* Temptable has at least one rowid */
1147
SJ_TMP_TABLE *sjtbl;
1148
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
1149
if (!(sjtbl= (SJ_TMP_TABLE*)thd->alloc(sizeof(SJ_TMP_TABLE))) ||
1150
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) thd->alloc(tabs_size)))
1152
memcpy(sjtbl->tabs, sjtabs, tabs_size);
1153
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
1154
sjtbl->rowid_len= jt_rowid_offset;
1155
sjtbl->null_bits= jt_null_bits;
1156
sjtbl->null_bytes= (jt_null_bits + 7)/8;
1158
*next_sjtbl_ptr= sjtbl;
1159
next_sjtbl_ptr= &(sjtbl->next);
1163
create_duplicate_weedout_tmp_table(thd,
1168
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
1169
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
1171
tab= last_outer_tab + 1;
1172
jump_to= last_outer_tab;
1175
/* Create the FirstMatch tail */
1176
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1178
if (tab->emb_sj_nest)
1179
tab->do_firstmatch= jump_to;
1188
static void cleanup_sj_tmp_tables(JOIN *join)
1190
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
1191
sj_tbl= sj_tbl->next)
1193
if (sj_tbl->tmp_table)
1195
sj_tbl->tmp_table->free_tmp_table(join->thd);
1198
join->sj_tmp_tables= NULL;
1201
uint32_t make_join_orderinfo(JOIN *join);
1204
global select optimisation.
1207
error code saved in field 'error'
1218
// to prevent double initialization on EXPLAIN
1223
thd->set_proc_info("optimizing");
1224
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
1225
unit->select_limit_cnt);
1226
/* select_limit is used to decide if we are likely to scan the whole table */
1227
select_limit= unit->select_limit_cnt;
1228
if (having || (select_options & OPTION_FOUND_ROWS))
1229
select_limit= HA_POS_ERROR;
1230
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
1231
// Ignore errors of execution if option IGNORE present
1232
if (thd->lex->ignore)
1233
thd->lex->current_select->no_error= 1;
1235
#ifdef HAVE_REF_TO_FIELDS // Not done yet
1236
/* Add HAVING to WHERE if possible */
1237
if (having && !group_list && !sum_func_count)
1244
else if ((conds=new Item_cond_and(conds,having)))
1247
Item_cond_and can't be fixed after creation, so we do not check
1250
conds->fix_fields(thd, &conds);
1251
conds->change_ref_to_fields(thd, tables_list);
1252
conds->top_level_item();
1258
/* Convert all outer joins to inner joins if possible */
1259
conds= simplify_joins(this, join_list, conds, true, false);
1260
build_bitmap_for_nested_joins(join_list, 0);
1262
conds= optimize_cond(this, conds, join_list, &cond_value);
1263
if (thd->is_error())
1270
having= optimize_cond(this, having, join_list, &having_value);
1271
if (thd->is_error())
1276
if (select_lex->where)
1277
select_lex->cond_value= cond_value;
1278
if (select_lex->having)
1279
select_lex->having_value= having_value;
1281
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
1282
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
1283
{ /* Impossible cond */
1284
zero_result_cause= having_value == Item::COND_FALSE ?
1285
"Impossible HAVING" : "Impossible WHERE";
1291
/* Optimize count(*), cmin() and cmax() */
1292
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
1296
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
1297
to the WHERE conditions,
1298
or 1 if all items were resolved,
1299
or 0, or an error number HA_ERR_...
1301
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
1303
if (res == HA_ERR_KEY_NOT_FOUND)
1305
zero_result_cause= "No matching min/max row";
1316
zero_result_cause= "No matching min/max row";
1320
zero_result_cause= "Select tables optimized away";
1321
tables_list= 0; // All tables resolved
1323
Extract all table-independent conditions and replace the WHERE
1324
clause with them. All other conditions were computed by opt_sum_query
1325
and the MIN/MAX/COUNT function(s) have been replaced by constants,
1326
so there is no need to compute the whole WHERE clause again.
1327
Notice that make_cond_for_table() will always succeed to remove all
1328
computed conditions, because opt_sum_query() is applicable only to
1330
Preserve conditions for EXPLAIN.
1332
if (conds && !(thd->lex->describe & DESCRIBE_EXTENDED))
1334
COND *table_independent_conds=
1335
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
1336
conds= table_independent_conds;
1345
error= -1; // Error is sent to client
1346
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
1348
/* Calculate how to do the join */
1349
thd->set_proc_info("statistics");
1350
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
1351
thd->is_fatal_error)
1356
/* Remove distinct if only const tables */
1357
select_distinct= select_distinct && (const_tables != tables);
1358
thd->set_proc_info("preparing");
1359
if (result->initialize_tables(this))
1361
return(1); // error == -1
1363
if (const_table_map != found_const_table_map &&
1364
!(select_options & SELECT_DESCRIBE) &&
1366
!(conds->used_tables() & RAND_TABLE_BIT) ||
1367
select_lex->master_unit() == &thd->lex->unit)) // upper level SELECT
1369
zero_result_cause= "no matching row in const table";
1373
if (!(thd->options & OPTION_BIG_SELECTS) &&
1374
best_read > (double) thd->variables.max_join_size &&
1375
!(select_options & SELECT_DESCRIBE))
1376
{ /* purecov: inspected */
1377
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
1381
if (const_tables && !thd->locked_tables &&
1382
!(select_options & SELECT_NO_UNLOCK))
1383
mysql_unlock_some_tables(thd, table, const_tables);
1384
if (!conds && outer_join)
1386
/* Handle the case where we have an OUTER JOIN without a WHERE */
1387
conds=new Item_int((int64_t) 1,1); // Always true
1389
select= make_select(*table, const_table_map,
1390
const_table_map, conds, 1, &error);
1392
{ /* purecov: inspected */
1393
error= -1; /* purecov: inspected */
1397
reset_nj_counters(join_list);
1398
make_outerjoin_info(this);
1401
Among the equal fields belonging to the same multiple equality
1402
choose the one that is to be retrieved first and substitute
1403
all references to these in where condition for a reference for
1408
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
1409
conds->update_used_tables();
1413
Permorm the the optimization on fields evaluation mentioned above
1414
for all on expressions.
1416
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
1418
if (*tab->on_expr_ref)
1420
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
1423
(*tab->on_expr_ref)->update_used_tables();
1427
if (conds &&!outer_join && const_table_map != found_const_table_map &&
1428
(select_options & SELECT_DESCRIBE) &&
1429
select_lex->master_unit() == &thd->lex->unit) // upper level SELECT
1431
conds=new Item_int((int64_t) 0,1); // Always false
1433
if (make_join_select(this, select, conds))
1436
"Impossible WHERE noticed after reading const tables";
1437
return(0); // error == 0
1440
error= -1; /* if goto err */
1442
/* Optimize distinct away if possible */
1444
order_st *org_order= order;
1445
order=remove_const(this, order,conds,1, &simple_order);
1446
if (thd->is_error())
1453
If we are using order_st BY NULL or order_st BY const_expression,
1454
return result in any order (even if we are using a GROUP BY)
1456
if (!order && org_order)
1460
Check if we can optimize away GROUP BY/DISTINCT.
1461
We can do that if there are no aggregate functions, the
1462
fields in DISTINCT clause (if present) and/or columns in GROUP BY
1463
(if present) contain direct references to all key parts of
1464
an unique index (in whatever order) and if the key parts of the
1465
unique index cannot contain NULLs.
1466
Note that the unique keys for DISTINCT and GROUP BY should not
1467
be the same (as long as they are unique).
1469
The FROM clause must contain a single non-constant table.
1471
if (tables - const_tables == 1 && (group_list || select_distinct) &&
1472
!tmp_table_param.sum_func_count &&
1473
(!join_tab[const_tables].select ||
1474
!join_tab[const_tables].select->quick ||
1475
join_tab[const_tables].select->quick->get_type() !=
1476
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
1479
list_contains_unique_index(join_tab[const_tables].table,
1480
find_field_in_order_list,
1481
(void *) group_list))
1484
We have found that grouping can be removed since groups correspond to
1485
only one row anyway, but we still have to guarantee correct result
1486
order. The line below effectively rewrites the query from GROUP BY
1487
<fields> to order_st BY <fields>. There are two exceptions:
1488
- if skip_sort_order is set (see above), then we can simply skip
1490
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
1491
with the GROUP BY ones, i.e. either one is a prefix of another.
1492
We only check if the order_st BY is a prefix of GROUP BY. In this case
1493
test_if_subpart() copies the ASC/DESC attributes from the original
1495
If GROUP BY is a prefix of order_st BY, then it is safe to leave
1498
if (!order || test_if_subpart(group_list, order))
1499
order= skip_sort_order ? 0 : group_list;
1501
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
1502
rewritten to IGNORE INDEX FOR order_st BY(fields).
1504
join_tab->table->keys_in_use_for_order_by=
1505
join_tab->table->keys_in_use_for_group_by;
1509
if (select_distinct &&
1510
list_contains_unique_index(join_tab[const_tables].table,
1511
find_field_in_item_list,
1512
(void *) &fields_list))
1517
if (group_list || tmp_table_param.sum_func_count)
1519
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
1522
else if (select_distinct && tables - const_tables == 1)
1525
We are only using one table. In this case we change DISTINCT to a
1527
- The GROUP BY can be done through indexes (no sort) and the order_st
1528
BY only uses selected fields.
1529
(In this case we can later optimize away GROUP BY and order_st BY)
1530
- We are scanning the whole table without LIMIT
1532
- We are using CALC_FOUND_ROWS
1533
- We are using an order_st BY that can't be optimized away.
1535
We don't want to use this optimization when we are using LIMIT
1536
because in this case we can just create a temporary table that
1537
holds LIMIT rows and stop when this table is full.
1539
JOIN_TAB *tab= &join_tab[const_tables];
1540
bool all_order_fields_used;
1542
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
1543
&tab->table->keys_in_use_for_order_by);
1544
if ((group_list=create_distinct_group(thd, select_lex->ref_pointer_array,
1545
order, fields_list, all_fields,
1546
&all_order_fields_used)))
1548
bool skip_group= (skip_sort_order &&
1549
test_if_skip_sort_order(tab, group_list, select_limit, 1,
1550
&tab->table->keys_in_use_for_group_by) != 0);
1551
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
1552
if ((skip_group && all_order_fields_used) ||
1553
select_limit == HA_POS_ERROR ||
1554
(order && !skip_sort_order))
1556
/* Change DISTINCT to GROUP BY */
1559
if (all_order_fields_used)
1561
if (order && skip_sort_order)
1564
Force MySQL to read the table in sorted order to get result in
1567
tmp_table_param.quick_group=0;
1571
group=1; // For end_write_group
1576
else if (thd->is_fatal_error) // End of memory
1581
order_st *old_group_list;
1582
group_list= remove_const(this, (old_group_list= group_list), conds,
1583
rollup.state == ROLLUP::STATE_NONE,
1585
if (thd->is_error())
1590
if (old_group_list && !group_list)
1593
if (!group_list && group)
1595
order=0; // The output has only one row
1597
select_distinct= 0; // No need in distinct for 1 row
1598
group_optimized_away= 1;
1601
calc_group_buffer(this, group_list);
1602
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
1604
if (test_if_subpart(group_list, order) ||
1605
(!group_list && tmp_table_param.sum_func_count))
1608
// Can't use sort on head table if using row cache
1618
Check if we need to create a temporary table.
1619
This has to be done if all tables are not already read (const tables)
1620
and one of the following conditions holds:
1621
- We are using DISTINCT (simple distinct's are already optimized away)
1622
- We are using an order_st BY or GROUP BY on fields not in the first table
1623
- We are using different order_st BY and GROUP BY orders
1624
- The user wants us to buffer the result.
1626
need_tmp= (const_tables != tables &&
1627
((select_distinct || !simple_order || !simple_group) ||
1628
(group_list && order) ||
1629
test(select_options & OPTION_BUFFER_RESULT)));
1631
uint32_t no_jbuf_after= make_join_orderinfo(this);
1632
uint64_t select_opts_for_readinfo=
1633
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
1635
sj_tmp_tables= NULL;
1636
if (!select_lex->sj_nests.is_empty())
1637
setup_semijoin_dups_elimination(this, select_opts_for_readinfo,
1640
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1641
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1644
/* Create all structures needed for materialized subquery execution. */
1645
if (setup_subquery_materialization())
1649
is this simple IN subquery?
1651
if (!group_list && !order &&
1652
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1653
tables == 1 && conds &&
1659
if (join_tab[0].type == JT_EQ_REF &&
1660
join_tab[0].ref.items[0]->name == in_left_expr_name)
1662
remove_subq_pushed_predicates(&where);
1663
save_index_subquery_explain_info(join_tab, where);
1664
join_tab[0].type= JT_UNIQUE_SUBQUERY;
1668
subselect_uniquesubquery_engine(thd,
1673
else if (join_tab[0].type == JT_REF &&
1674
join_tab[0].ref.items[0]->name == in_left_expr_name)
1676
remove_subq_pushed_predicates(&where);
1677
save_index_subquery_explain_info(join_tab, where);
1678
join_tab[0].type= JT_INDEX_SUBQUERY;
1682
subselect_indexsubquery_engine(thd,
1689
} else if (join_tab[0].type == JT_REF_OR_NULL &&
1690
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1691
having->name == in_having_cond)
1693
join_tab[0].type= JT_INDEX_SUBQUERY;
1695
conds= remove_additional_cond(conds);
1696
save_index_subquery_explain_info(join_tab, conds);
1698
change_engine(new subselect_indexsubquery_engine(thd,
1708
Need to tell handlers that to play it safe, it should fetch all
1709
columns of the primary key of the tables: this is because MySQL may
1710
build row pointers for the rows, and for all columns of the primary key
1711
the read set has not necessarily been set by the server code.
1713
if (need_tmp || select_distinct || group_list || order)
1715
for (uint32_t i = const_tables; i < tables; i++)
1716
join_tab[i].table->prepare_for_position();
1719
if (const_tables != tables)
1722
Because filesort always does a full table scan or a quick range scan
1723
we must add the removed reference to the select for the table.
1724
We only need to do this when we have a simple_order or simple_group
1725
as in other cases the join is done before the sort.
1727
if ((order || group_list) &&
1728
(join_tab[const_tables].type != JT_ALL) &&
1729
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
1730
((order && simple_order) || (group_list && simple_group)))
1732
if (add_ref_to_table_cond(thd,&join_tab[const_tables])) {
1737
if (!(select_options & SELECT_BIG_RESULT) &&
1740
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1741
unit->select_limit_cnt, 0,
1742
&join_tab[const_tables].table->
1743
keys_in_use_for_group_by))) ||
1745
tmp_table_param.quick_group)
1747
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1752
Force using of tmp table if sorting by a SP or UDF function due to
1753
their expensive and probably non-deterministic nature.
1755
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1757
Item *item= *tmp_order->item;
1758
if (item->is_expensive())
1760
/* Force tmp table without sort */
1761
need_tmp=1; simple_order=simple_group=0;
1769
if (select_options & SELECT_DESCRIBE)
1777
The loose index scan access method guarantees that all grouping or
1778
duplicate row elimination (for distinct) is already performed
1779
during data retrieval, and that all MIN/MAX functions are already
1780
computed for each group. Thus all MIN/MAX functions should be
1781
treated as regular functions, and there is no need to perform
1782
grouping in the main execution loop.
1783
Notice that currently loose index scan is applicable only for
1784
single table queries, thus it is sufficient to test only the first
1785
join_tab element of the plan for its access method.
1787
if (join_tab->is_using_loose_index_scan())
1788
tmp_table_param.precomputed_group_by= true;
1790
/* Create a tmp table if distinct or if the sort is too complicated */
1793
thd->set_proc_info("Creating tmp table");
1795
init_items_ref_array();
1797
tmp_table_param.hidden_field_count= (all_fields.elements -
1798
fields_list.elements);
1799
order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1802
Pushing LIMIT to the temporary table creation is not applicable
1803
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1804
there are aggregate functions, because in all these cases we need
1807
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1809
!thd->lex->current_select->with_sum_func) ?
1810
select_limit : HA_POS_ERROR;
1812
if (!(exec_tmp_table1=
1813
create_tmp_table(thd, &tmp_table_param, all_fields,
1815
group_list ? 0 : select_distinct,
1816
group_list && simple_group,
1825
We don't have to store rows in temp table that doesn't match HAVING if:
1826
- we are sorting the table and writing complete group rows to the
1828
- We are using DISTINCT without resolving the distinct as a GROUP BY
1831
If having is not handled here, it will be checked before the row
1832
is sent to the client.
1835
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1838
/* if group or order on first table, sort first */
1839
if (group_list && simple_group)
1841
thd->set_proc_info("Sorting for group");
1842
if (create_sort_index(thd, this, group_list,
1843
HA_POS_ERROR, HA_POS_ERROR, false) ||
1844
alloc_group_fields(this, group_list) ||
1845
make_sum_func_list(all_fields, fields_list, 1) ||
1846
setup_sum_funcs(thd, sum_funcs))
1854
if (make_sum_func_list(all_fields, fields_list, 0) ||
1855
setup_sum_funcs(thd, sum_funcs))
1860
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1862
thd->set_proc_info("Sorting for order");
1863
if (create_sort_index(thd, this, order,
1864
HA_POS_ERROR, HA_POS_ERROR, true))
1873
Optimize distinct when used on some of the tables
1874
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1875
In this case we can stop scanning t2 when we have found one t1.a
1878
if (exec_tmp_table1->distinct)
1880
table_map used_tables= thd->used_tables;
1881
JOIN_TAB *last_join_tab= join_tab+tables-1;
1884
if (used_tables & last_join_tab->table->map)
1886
last_join_tab->not_used_in_distinct=1;
1887
} while (last_join_tab-- != join_tab);
1888
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1889
if (order && skip_sort_order)
1891
/* Should always succeed */
1892
if (test_if_skip_sort_order(&join_tab[const_tables],
1893
order, unit->select_limit_cnt, 0,
1894
&join_tab[const_tables].table->
1895
keys_in_use_for_order_by))
1901
If this join belongs to an uncacheable subquery save
1904
if (select_lex->uncacheable && !is_top_level_join() &&
1905
init_save_join_tab())
1906
return(-1); /* purecov: inspected */
1915
Restore values in temporary join.
1917
void JOIN::restore_tmp()
1919
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1926
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1927
select_lex->offset_limit->val_uint() :
1932
if (exec_tmp_table1)
1934
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1935
exec_tmp_table1->file->ha_delete_all_rows();
1936
free_io_cache(exec_tmp_table1);
1937
filesort_free_buffers(exec_tmp_table1,0);
1939
if (exec_tmp_table2)
1941
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1942
exec_tmp_table2->file->ha_delete_all_rows();
1943
free_io_cache(exec_tmp_table2);
1944
filesort_free_buffers(exec_tmp_table2,0);
1947
set_items_ref_array(items0);
1950
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1955
/* Reset of sum functions */
1958
Item_sum *func, **func_ptr= sum_funcs;
1959
while ((func= *(func_ptr++)))
1967
@brief Save the original join layout
1969
@details Saves the original join layout so it can be reused in
1970
re-execution and for EXPLAIN.
1972
@return Operation status
1974
@retval 1 error occurred.
1978
JOIN::init_save_join_tab()
1980
if (!(tmp_join= (JOIN*)thd->alloc(sizeof(JOIN))))
1981
return 1; /* purecov: inspected */
1982
error= 0; // Ensure that tmp_join.error= 0
1989
JOIN::save_join_tab()
1991
if (!join_tab_save && select_lex->master_unit()->uncacheable)
1993
if (!(join_tab_save= (JOIN_TAB*)thd->memdup((unsigned char*) join_tab,
1994
sizeof(JOIN_TAB) * tables)))
2005
Note, that create_sort_index calls test_if_skip_sort_order and may
2006
finally replace sorting with index scan if there is a LIMIT clause in
2007
the query. It's never shown in EXPLAIN!
2010
When can we have here thd->net.report_error not zero?
2015
List<Item> *columns_list= &fields_list;
2018
thd->set_proc_info("executing");
2020
(void) result->prepare2(); // Currently, this cannot fail.
2022
if (!tables_list && (tables || !select_lex->with_sum_func))
2023
{ // Only test of functions
2024
if (select_options & SELECT_DESCRIBE)
2025
select_describe(this, false, false, false,
2026
(zero_result_cause?zero_result_cause:"No tables used"));
2029
result->send_fields(*columns_list,
2030
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2032
We have to test for 'conds' here as the WHERE may not be constant
2033
even if we don't have any tables for prepared statements or if
2034
conds uses something like 'rand()'.
2036
if (cond_value != Item::COND_FALSE &&
2037
(!conds || conds->val_int()) &&
2038
(!having || having->val_int()))
2040
if (do_send_rows && result->send_data(fields_list))
2044
error= (int) result->send_eof();
2045
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 :
2046
thd->sent_row_count);
2051
error=(int) result->send_eof();
2055
/* Single select (without union) always returns 0 or 1 row */
2056
thd->limit_found_rows= send_records;
2057
thd->examined_row_count= 0;
2061
Don't reset the found rows count if there're no tables as
2062
FOUND_ROWS() may be called. Never reset the examined row count here.
2063
It must be accumulated from all join iterations of all join parts.
2066
thd->limit_found_rows= 0;
2068
if (zero_result_cause)
2070
(void) return_zero_rows(this, result, select_lex->leaf_tables,
2072
send_row_on_empty_set(),
2079
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) &&
2080
get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
2083
if (select_options & SELECT_DESCRIBE)
2086
Check if we managed to optimize order_st BY away and don't use temporary
2087
table to resolve order_st BY: in that case, we only may need to do
2088
filesort for GROUP BY.
2090
if (!order && !no_order && (!skip_sort_order || !need_tmp))
2093
Reset 'order' to 'group_list' and reinit variables describing
2097
simple_order= simple_group;
2101
(order != group_list || !(select_options & SELECT_BIG_RESULT)) &&
2102
(const_tables == tables ||
2103
((simple_order || skip_sort_order) &&
2104
test_if_skip_sort_order(&join_tab[const_tables], order,
2106
&join_tab[const_tables].table->
2107
keys_in_use_for_query))))
2110
select_describe(this, need_tmp,
2111
order != 0 && !skip_sort_order,
2113
!tables ? "No tables used" : NULL);
2117
JOIN *curr_join= this;
2118
List<Item> *curr_all_fields= &all_fields;
2119
List<Item> *curr_fields_list= &fields_list;
2120
Table *curr_tmp_table= 0;
2122
Initialize examined rows here because the values from all join parts
2123
must be accumulated in examined_row_count. Hence every join
2124
iteration must count from zero.
2126
curr_join->examined_rows= 0;
2128
/* Create a tmp table if distinct or if the sort is too complicated */
2134
We are in a non cacheable sub query. Get the saved join structure
2136
(curr_join may have been modified during last exection and we need
2139
curr_join= tmp_join;
2141
curr_tmp_table= exec_tmp_table1;
2143
/* Copy data to the temporary table */
2144
thd->set_proc_info("Copying to tmp table");
2145
if (!curr_join->sort_and_group &&
2146
curr_join->const_tables != curr_join->tables)
2147
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2148
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2153
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
2155
if (curr_join->having)
2156
curr_join->having= curr_join->tmp_having= 0; // Allready done
2158
/* Change sum_fields reference to calculated fields in tmp_table */
2159
curr_join->all_fields= *curr_all_fields;
2162
items1= items0 + all_fields.elements;
2163
if (sort_and_group || curr_tmp_table->group)
2165
if (change_to_use_tmp_fields(thd, items1,
2166
tmp_fields_list1, tmp_all_fields1,
2167
fields_list.elements, all_fields))
2172
if (change_refs_to_tmp_fields(thd, items1,
2173
tmp_fields_list1, tmp_all_fields1,
2174
fields_list.elements, all_fields))
2177
curr_join->tmp_all_fields1= tmp_all_fields1;
2178
curr_join->tmp_fields_list1= tmp_fields_list1;
2179
curr_join->items1= items1;
2181
curr_all_fields= &tmp_all_fields1;
2182
curr_fields_list= &tmp_fields_list1;
2183
curr_join->set_items_ref_array(items1);
2185
if (sort_and_group || curr_tmp_table->group)
2187
curr_join->tmp_table_param.field_count+=
2188
curr_join->tmp_table_param.sum_func_count+
2189
curr_join->tmp_table_param.func_count;
2190
curr_join->tmp_table_param.sum_func_count=
2191
curr_join->tmp_table_param.func_count= 0;
2195
curr_join->tmp_table_param.field_count+=
2196
curr_join->tmp_table_param.func_count;
2197
curr_join->tmp_table_param.func_count= 0;
2200
if (curr_tmp_table->group)
2201
{ // Already grouped
2202
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
2203
curr_join->order= curr_join->group_list; /* order by group */
2204
curr_join->group_list= 0;
2208
If we have different sort & group then we must sort the data by group
2209
and copy it to another tmp table
2210
This code is also used if we are using distinct something
2211
we haven't been able to store in the temporary table yet
2212
like SEC_TO_TIME(SUM(...)).
2215
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct)) || (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
2216
{ /* Must copy to another table */
2217
/* Free first data from old join */
2218
curr_join->join_free();
2219
if (make_simple_join(curr_join, curr_tmp_table))
2221
calc_group_buffer(curr_join, group_list);
2222
count_field_types(select_lex, &curr_join->tmp_table_param,
2223
curr_join->tmp_all_fields1,
2224
curr_join->select_distinct && !curr_join->group_list);
2225
curr_join->tmp_table_param.hidden_field_count=
2226
(curr_join->tmp_all_fields1.elements-
2227
curr_join->tmp_fields_list1.elements);
2230
if (exec_tmp_table2)
2231
curr_tmp_table= exec_tmp_table2;
2234
/* group data to new table */
2237
If the access method is loose index scan then all MIN/MAX
2238
functions are precomputed, and should be treated as regular
2239
functions. See extended comment in JOIN::exec.
2241
if (curr_join->join_tab->is_using_loose_index_scan())
2242
curr_join->tmp_table_param.precomputed_group_by= true;
2244
if (!(curr_tmp_table=
2245
exec_tmp_table2= create_tmp_table(thd,
2246
&curr_join->tmp_table_param,
2249
curr_join->select_distinct &&
2250
!curr_join->group_list,
2251
1, curr_join->select_options,
2255
curr_join->exec_tmp_table2= exec_tmp_table2;
2257
if (curr_join->group_list)
2259
thd->set_proc_info("Creating sort index");
2260
if (curr_join->join_tab == join_tab && save_join_tab())
2264
if (create_sort_index(thd, curr_join, curr_join->group_list,
2265
HA_POS_ERROR, HA_POS_ERROR, false) ||
2266
make_group_fields(this, curr_join))
2270
sortorder= curr_join->sortorder;
2273
thd->set_proc_info("Copying to group table");
2275
if (curr_join != this)
2279
curr_join->sum_funcs= sum_funcs2;
2280
curr_join->sum_funcs_end= sum_funcs_end2;
2284
curr_join->alloc_func_list();
2285
sum_funcs2= curr_join->sum_funcs;
2286
sum_funcs_end2= curr_join->sum_funcs_end;
2289
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2292
curr_join->group_list= 0;
2293
if (!curr_join->sort_and_group &&
2294
curr_join->const_tables != curr_join->tables)
2295
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2296
if (setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) ||
2297
(tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2302
end_read_record(&curr_join->join_tab->read_record);
2303
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
2304
curr_join->join_tab[0].table= 0; // Table is freed
2306
// No sum funcs anymore
2309
items2= items1 + all_fields.elements;
2310
if (change_to_use_tmp_fields(thd, items2,
2311
tmp_fields_list2, tmp_all_fields2,
2312
fields_list.elements, tmp_all_fields1))
2314
curr_join->tmp_fields_list2= tmp_fields_list2;
2315
curr_join->tmp_all_fields2= tmp_all_fields2;
2317
curr_fields_list= &curr_join->tmp_fields_list2;
2318
curr_all_fields= &curr_join->tmp_all_fields2;
2319
curr_join->set_items_ref_array(items2);
2320
curr_join->tmp_table_param.field_count+=
2321
curr_join->tmp_table_param.sum_func_count;
2322
curr_join->tmp_table_param.sum_func_count= 0;
2324
if (curr_tmp_table->distinct)
2325
curr_join->select_distinct=0; /* Each row is unique */
2327
curr_join->join_free(); /* Free quick selects */
2328
if (curr_join->select_distinct && ! curr_join->group_list)
2330
thd->set_proc_info("Removing duplicates");
2331
if (curr_join->tmp_having)
2332
curr_join->tmp_having->update_used_tables();
2333
if (remove_duplicates(curr_join, curr_tmp_table,
2334
*curr_fields_list, curr_join->tmp_having))
2336
curr_join->tmp_having=0;
2337
curr_join->select_distinct=0;
2339
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
2340
if (make_simple_join(curr_join, curr_tmp_table))
2342
calc_group_buffer(curr_join, curr_join->group_list);
2343
count_field_types(select_lex, &curr_join->tmp_table_param,
2344
*curr_all_fields, 0);
2348
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
2350
if (make_group_fields(this, curr_join))
2357
init_items_ref_array();
2358
items3= ref_pointer_array + (all_fields.elements*4);
2359
setup_copy_fields(thd, &curr_join->tmp_table_param,
2360
items3, tmp_fields_list3, tmp_all_fields3,
2361
curr_fields_list->elements, *curr_all_fields);
2362
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
2363
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
2364
tmp_table_param.save_copy_field_end=
2365
curr_join->tmp_table_param.copy_field_end;
2366
curr_join->tmp_all_fields3= tmp_all_fields3;
2367
curr_join->tmp_fields_list3= tmp_fields_list3;
2371
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
2372
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
2373
curr_join->tmp_table_param.copy_field_end=
2374
tmp_table_param.save_copy_field_end;
2376
curr_fields_list= &tmp_fields_list3;
2377
curr_all_fields= &tmp_all_fields3;
2378
curr_join->set_items_ref_array(items3);
2380
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2382
setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) ||
2383
thd->is_fatal_error)
2386
if (curr_join->group_list || curr_join->order)
2388
thd->set_proc_info("Sorting result");
2389
/* If we have already done the group, add HAVING to sorted table */
2390
if (curr_join->tmp_having && ! curr_join->group_list &&
2391
! curr_join->sort_and_group)
2393
// Some tables may have been const
2394
curr_join->tmp_having->update_used_tables();
2395
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
2396
table_map used_tables= (curr_join->const_table_map |
2397
curr_table->table->map);
2399
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having,
2402
if (sort_table_cond)
2404
if (!curr_table->select)
2405
if (!(curr_table->select= new SQL_SELECT))
2407
if (!curr_table->select->cond)
2408
curr_table->select->cond= sort_table_cond;
2409
else // This should never happen
2411
if (!(curr_table->select->cond=
2412
new Item_cond_and(curr_table->select->cond,
2416
Item_cond_and do not need fix_fields for execution, its parameters
2417
are fixed or do not need fix_fields, too
2419
curr_table->select->cond->quick_fix_field();
2421
curr_table->select_cond= curr_table->select->cond;
2422
curr_table->select_cond->top_level_item();
2423
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
2430
curr_join->select_limit= HA_POS_ERROR;
2434
We can abort sorting after thd->select_limit rows if we there is no
2435
WHERE clause for any tables after the sorted one.
2437
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
2438
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
2439
for (; curr_table < end_table ; curr_table++)
2442
table->keyuse is set in the case there was an original WHERE clause
2443
on the table that was optimized away.
2445
if (curr_table->select_cond ||
2446
(curr_table->keyuse && !curr_table->first_inner))
2448
/* We have to sort all rows */
2449
curr_join->select_limit= HA_POS_ERROR;
2454
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(thd, 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))
2475
sortorder= curr_join->sortorder;
2476
if (curr_join->const_tables != curr_join->tables &&
2477
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
2480
If no IO cache exists for the first table then we are using an
2481
INDEX SCAN and no filesort. Thus we should not remove the sorted
2482
attribute on the INDEX SCAN.
2488
/* XXX: When can we have here thd->is_error() not zero? */
2489
if (thd->is_error())
2491
error= thd->is_error();
2494
curr_join->having= curr_join->tmp_having;
2495
curr_join->fields= curr_fields_list;
2498
thd->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
thd->limit_found_rows= curr_join->send_records;
2505
/* Accumulate the counts from all join iterations of all join parts. */
2506
thd->examined_row_count+= curr_join->examined_rows;
2509
With EXPLAIN EXTENDED we have to restore original ref_array
2510
for a derived table which is always materialized.
2511
Otherwise we would not be able to print the query correctly.
2514
(thd->lex->describe & DESCRIBE_EXTENDED) &&
2515
select_lex->linkage == DERIVED_TABLE_TYPE)
2516
set_items_ref_array(items0);
2526
Return error that hold JOIN.
2532
select_lex->join= 0;
2536
if (join_tab != tmp_join->join_tab)
2538
JOIN_TAB *tab, *end;
2539
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
2542
tmp_join->tmp_join= 0;
2543
tmp_table_param.copy_field=0;
2544
return(tmp_join->destroy());
2549
if (exec_tmp_table1)
2550
exec_tmp_table1->free_tmp_table(thd);
2551
if (exec_tmp_table2)
2552
exec_tmp_table2->free_tmp_table(thd);
2554
delete_dynamic(&keyuse);
310
2561
An entry point to single-unit select (a select without UNION).
312
@param session thread Cursor
2563
@param thd thread handler
313
2564
@param rref_pointer_array a reference to ref_pointer_array of
314
2565
the top-level select_lex for this query
315
2566
@param tables list of all tables used in this query.
316
2567
The tables have been pre-opened.
317
@param wild_num number of wildcards used in the top level
2568
@param wild_num number of wildcards used in the top level
318
2569
select of this query.
319
2570
For example statement
320
2571
SELECT *, t1.*, catalog.t2.* FROM t0, t1, t2;
441
session->set_proc_info("end");
2695
thd->set_proc_info("end");
442
2696
err|= select_lex->cleanup();
443
return(err || session->is_error());
2697
return(err || thd->is_error());
445
2699
return(join->error);
448
inline Item *and_items(Item* cond, Item *item)
2703
int subq_sj_candidate_cmp(Item_in_subselect* const *el1,
2704
Item_in_subselect* const *el2)
2706
return ((*el1)->sj_convert_priority < (*el2)->sj_convert_priority) ? 1 :
2707
( ((*el1)->sj_convert_priority == (*el2)->sj_convert_priority)? 0 : -1);
2711
inline Item * and_items(Item* cond, Item *item)
450
2713
return (cond? (new Item_cond_and(cond, item)) : item);
2717
static TableList *alloc_join_nest(THD *thd)
2720
if (!(tbl= (TableList*) thd->calloc(ALIGN_SIZE(sizeof(TableList))+
2721
sizeof(nested_join_st))))
2723
tbl->nested_join= (nested_join_st*) ((unsigned char*)tbl +
2724
ALIGN_SIZE(sizeof(TableList)));
2729
void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TableList> *tlist)
2731
List_iterator<TableList> it(*tlist);
2733
while ((table= it++))
2736
table->on_expr->fix_after_pullout(new_parent, &table->on_expr);
2737
if (table->nested_join)
2738
fix_list_after_tbl_changes(new_parent, &table->nested_join->join_list);
2744
Convert a subquery predicate into a TableList semi-join nest
2747
convert_subq_to_sj()
2748
parent_join Parent join, the one that has subq_pred in its WHERE/ON
2750
subq_pred Subquery predicate to be converted
2753
Convert a subquery predicate into a TableList semi-join nest. All the
2754
prerequisites are already checked, so the conversion is always successfull.
2756
Prepared Statements: the transformation is permanent:
2757
- Changes in TableList structures are naturally permanent
2758
- Item tree changes are performed on statement MEM_ROOT:
2759
= we activate statement MEM_ROOT
2760
= this function is called before the first fix_prepare_information
2763
This is intended because the criteria for subquery-to-sj conversion remain
2764
constant for the lifetime of the Prepared Statement.
2768
true Out of memory error
2771
bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
2773
SELECT_LEX *parent_lex= parent_join->select_lex;
2774
TableList *emb_tbl_nest= NULL;
2775
List<TableList> *emb_join_list= &parent_lex->top_join_list;
2776
THD *thd= parent_join->thd;
2779
1. Find out where to put the predicate into.
2780
Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
2782
if ((void*)subq_pred->expr_join_nest != (void*)1)
2784
if (subq_pred->expr_join_nest->nested_join)
2789
... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
2791
The sj-nest will be inserted into the brackets nest.
2793
emb_tbl_nest= subq_pred->expr_join_nest;
2794
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2796
else if (!subq_pred->expr_join_nest->outer_join)
2801
... INNER JOIN tblX ON (subquery AND whatever) ...
2803
The sj-nest will be tblX's "sibling", i.e. another child of its
2804
parent. This is ok because tblX is joined as an inner join.
2806
emb_tbl_nest= subq_pred->expr_join_nest->embedding;
2808
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2810
else if (!subq_pred->expr_join_nest->nested_join)
2812
TableList *outer_tbl= subq_pred->expr_join_nest;
2813
TableList *wrap_nest;
2817
... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
2819
we'll need to convert it into:
2821
... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
2823
|<----- wrap_nest ---->|
2825
Q: other subqueries may be pointing to this element. What to do?
2826
A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
2827
But we'll need to fix other pointers.
2828
A2: Another way: have TableList::next_ptr so the following
2829
subqueries know the table has been nested.
2830
A3: changes in the TableList::outer_join will make everything work
2833
if (!(wrap_nest= alloc_join_nest(parent_join->thd)))
2837
wrap_nest->embedding= outer_tbl->embedding;
2838
wrap_nest->join_list= outer_tbl->join_list;
2839
wrap_nest->alias= (char*) "(sj-wrap)";
2841
wrap_nest->nested_join->join_list.empty();
2842
wrap_nest->nested_join->join_list.push_back(outer_tbl);
2844
outer_tbl->embedding= wrap_nest;
2845
outer_tbl->join_list= &wrap_nest->nested_join->join_list;
2848
wrap_nest will take place of outer_tbl, so move the outer join flag
2851
wrap_nest->outer_join= outer_tbl->outer_join;
2852
outer_tbl->outer_join= 0;
2854
wrap_nest->on_expr= outer_tbl->on_expr;
2855
outer_tbl->on_expr= NULL;
2857
List_iterator<TableList> li(*wrap_nest->join_list);
2861
if (tbl == outer_tbl)
2863
li.replace(wrap_nest);
2868
Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
2869
semi-join nest into it
2871
emb_join_list= &wrap_nest->nested_join->join_list;
2872
emb_tbl_nest= wrap_nest;
2877
nested_join_st *nested_join;
2878
if (!(sj_nest= alloc_join_nest(parent_join->thd)))
2882
nested_join= sj_nest->nested_join;
2884
sj_nest->join_list= emb_join_list;
2885
sj_nest->embedding= emb_tbl_nest;
2886
sj_nest->alias= (char*) "(sj-nest)";
2887
/* Nests do not participate in those 'chains', so: */
2888
/* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
2889
emb_join_list->push_back(sj_nest);
2892
nested_join->used_tables and nested_join->not_null_tables are
2893
initialized in simplify_joins().
2897
2. Walk through subquery's top list and set 'embedding' to point to the
2900
st_select_lex *subq_lex= subq_pred->unit->first_select();
2901
nested_join->join_list.empty();
2902
List_iterator_fast<TableList> li(subq_lex->top_join_list);
2903
TableList *tl, *last_leaf;
2906
tl->embedding= sj_nest;
2907
tl->join_list= &nested_join->join_list;
2908
nested_join->join_list.push_back(tl);
2912
Reconnect the next_leaf chain.
2913
TODO: Do we have to put subquery's tables at the end of the chain?
2914
Inserting them at the beginning would be a bit faster.
2915
NOTE: We actually insert them at the front! That's because the order is
2916
reversed in this list.
2918
for (tl= parent_lex->leaf_tables; tl->next_leaf; tl= tl->next_leaf) {};
2919
tl->next_leaf= subq_lex->leaf_tables;
2923
Same as above for next_local chain
2924
(a theory: a next_local chain always starts with ::leaf_tables
2925
because view's tables are inserted after the view)
2927
for (tl= parent_lex->leaf_tables; tl->next_local; tl= tl->next_local) {};
2928
tl->next_local= subq_lex->leaf_tables;
2930
/* A theory: no need to re-connect the next_global chain */
2932
/* 3. Remove the original subquery predicate from the WHERE/ON */
2934
// The subqueries were replaced for Item_int(1) earlier
2935
subq_pred->exec_method= Item_in_subselect::SEMI_JOIN; // for subsequent executions
2936
/*TODO: also reset the 'with_subselect' there. */
2938
/* n. Adjust the parent_join->tables counter */
2939
uint32_t table_no= parent_join->tables;
2940
/* n. Walk through child's tables and adjust table->map */
2941
for (tl= subq_lex->leaf_tables; tl; tl= tl->next_leaf, table_no++)
2943
tl->table->tablenr= table_no;
2944
tl->table->map= ((table_map)1) << table_no;
2945
SELECT_LEX *old_sl= tl->select_lex;
2946
tl->select_lex= parent_join->select_lex;
2947
for(TableList *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)
2948
emb->select_lex= parent_join->select_lex;
2950
parent_join->tables += subq_lex->join->tables;
2953
Put the subquery's WHERE into semi-join's sj_on_expr
2954
Add the subquery-induced equalities too.
2956
SELECT_LEX *save_lex= thd->lex->current_select;
2957
thd->lex->current_select=subq_lex;
2958
if (!subq_pred->left_expr->fixed &&
2959
subq_pred->left_expr->fix_fields(thd, &subq_pred->left_expr))
2961
thd->lex->current_select=save_lex;
2963
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
2964
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables() |
2965
subq_pred->left_expr->used_tables();
2966
sj_nest->sj_on_expr= subq_lex->where;
2969
Create the IN-equalities and inject them into semi-join's ON expression.
2970
Additionally, for InsideOut strategy
2971
- Record the number of IN-equalities.
2972
- Create list of pointers to (oe1, ..., ieN). We'll need the list to
2973
see which of the expressions are bound and which are not (for those
2974
we'll produce a distinct stream of (ie_i1,...ie_ik).
2976
(TODO: can we just create a list of pointers and hope the expressions
2977
will not substitute themselves on fix_fields()? or we need to wrap
2978
them into Item_direct_view_refs and store pointers to those. The
2979
pointers to Item_direct_view_refs are guaranteed to be stable as
2980
Item_direct_view_refs doesn't substitute itself with anything in
2981
Item_direct_view_ref::fix_fields.
2983
sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
2984
sj_nest->nested_join->sj_outer_expr_list.empty();
2986
if (subq_pred->left_expr->cols() == 1)
2988
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr);
2990
Item *item_eq= new Item_func_eq(subq_pred->left_expr,
2991
subq_lex->ref_pointer_array[0]);
2992
item_eq->name= (char*)subq_sj_cond_name;
2993
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
2997
for (uint32_t i= 0; i < subq_pred->left_expr->cols(); i++)
2999
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->
3002
new Item_func_eq(subq_pred->left_expr->element_index(i),
3003
subq_lex->ref_pointer_array[i]);
3004
item_eq->name= (char*)subq_sj_cond_name + (i % 64);
3005
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3008
/* Fix the created equality and AND */
3009
sj_nest->sj_on_expr->fix_fields(parent_join->thd, &sj_nest->sj_on_expr);
3012
Walk through sj nest's WHERE and ON expressions and call
3013
item->fix_table_changes() for all items.
3015
sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr);
3016
fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
3019
/* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
3020
subq_lex->master_unit()->exclude_level();
3022
/* Inject sj_on_expr into the parent's WHERE or ON */
3025
emb_tbl_nest->on_expr= and_items(emb_tbl_nest->on_expr,
3026
sj_nest->sj_on_expr);
3027
emb_tbl_nest->on_expr->fix_fields(parent_join->thd, &emb_tbl_nest->on_expr);
3031
/* Inject into the WHERE */
3032
parent_join->conds= and_items(parent_join->conds, sj_nest->sj_on_expr);
3033
parent_join->conds->fix_fields(parent_join->thd, &parent_join->conds);
3034
parent_join->select_lex->where= parent_join->conds;
3042
Convert candidate subquery predicates to semi-joins
3045
JOIN::flatten_subqueries()
3048
Convert candidate subquery predicates to semi-joins.
3055
bool JOIN::flatten_subqueries()
3057
Item_in_subselect **in_subq;
3058
Item_in_subselect **in_subq_end;
3060
if (sj_subselects.elements() == 0)
3063
/* 1. Fix children subqueries */
3064
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
3065
in_subq != in_subq_end; in_subq++)
3067
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3068
child_join->outer_tables = child_join->tables;
3069
if (child_join->flatten_subqueries())
3071
(*in_subq)->sj_convert_priority=
3072
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
3075
//dump_TableList_struct(select_lex, select_lex->leaf_tables);
3077
2. Pick which subqueries to convert:
3078
sort the subquery array
3079
- prefer correlated subqueries over uncorrelated;
3080
- prefer subqueries that have greater number of outer tables;
3082
sj_subselects.sort(subq_sj_candidate_cmp);
3083
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
3084
/* Replace all subqueries to be flattened with Item_int(1) */
3085
for (in_subq= sj_subselects.front();
3086
in_subq != in_subq_end &&
3087
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3090
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
3094
for (in_subq= sj_subselects.front();
3095
in_subq != in_subq_end &&
3096
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3099
if (convert_subq_to_sj(this, *in_subq))
3103
/* 3. Finalize those we didn't convert */
3104
for (; in_subq!= in_subq_end; in_subq++)
3106
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3107
Item_subselect::trans_res res;
3108
(*in_subq)->changed= 0;
3109
(*in_subq)->fixed= 0;
3110
res= (*in_subq)->select_transformer(child_join);
3111
if (res == Item_subselect::RES_ERROR)
3114
(*in_subq)->changed= 1;
3115
(*in_subq)->fixed= 1;
3117
Item *substitute= (*in_subq)->substitution;
3118
bool do_fix_fields= !(*in_subq)->substitution->fixed;
3119
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
3122
//if ((*in_subq)->fix_fields(thd, (*in_subq)->ref_ptr))
3125
sj_subselects.clear();
3131
Setup for execution all subqueries of a query, for which the optimizer
3132
chose hash semi-join.
3134
@details Iterate over all subqueries of the query, and if they are under an
3135
IN predicate, and the optimizer chose to compute it via hash semi-join:
3136
- try to initialize all data structures needed for the materialized execution
3137
of the IN predicate,
3138
- if this fails, then perform the IN=>EXISTS transformation which was
3139
previously blocked during JOIN::prepare.
3141
This method is part of the "code generation" query processing phase.
3143
This phase must be called after substitute_for_best_equal_field() because
3144
that function may replace items with other items from a multiple equality,
3145
and we need to reference the correct items in the index access method of the
3148
@return Operation status
3149
@retval false success.
3150
@retval true error occurred.
3153
bool JOIN::setup_subquery_materialization()
3155
for (SELECT_LEX_UNIT *un= select_lex->first_inner_unit(); un;
3156
un= un->next_unit())
3158
for (SELECT_LEX *sl= un->first_select(); sl; sl= sl->next_select())
3160
Item_subselect *subquery_predicate= sl->master_unit()->item;
3161
if (subquery_predicate &&
3162
subquery_predicate->substype() == Item_subselect::IN_SUBS)
3164
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
3165
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
3166
in_subs->setup_engine())
3176
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3179
find_eq_ref_candidate()
3180
table Table to be checked
3181
sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
3185
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3188
Check again if it is feasible to factor common parts with constant table
3192
true - There exists an eq_ref(outer-tables) candidate
3196
bool find_eq_ref_candidate(Table *table, table_map sj_inner_tables)
3198
KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
3203
while (1) /* For each key */
3206
KEY *keyinfo= table->key_info + key;
3207
key_part_map bound_parts= 0;
3208
if ((keyinfo->flags & HA_NOSAME) == HA_NOSAME)
3210
do /* For all equalities on all key parts */
3212
/* Check if this is "t.keypart = expr(outer_tables) */
3213
if (!(keyuse->used_tables & sj_inner_tables) &&
3214
!(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
3216
bound_parts |= 1 << keyuse->keypart;
3219
} while (keyuse->key == key && keyuse->table == table);
3221
if (bound_parts == PREV_BITS(uint, keyinfo->key_parts))
3223
if (keyuse->table != table)
3231
if (keyuse->table != table)
3234
while (keyuse->key == key);
3243
Pull tables out of semi-join nests, if possible
3246
pull_out_semijoin_tables()
3247
join The join where to do the semi-join flattening
3250
Try to pull tables out of semi-join nests.
3253
When this function is called, the join may have several semi-join nests
3254
(possibly within different semi-join nests), but it is guaranteed that
3255
one semi-join nest does not contain another.
3258
A table can be pulled out of the semi-join nest if
3259
- It is a constant table
3263
* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer
3265
* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.
3266
* Semi-join nests TableList::sj_inner_tables
3268
This operation is (and should be) performed at each PS execution since
3269
tables may become/cease to be constant across PS reexecutions.
3273
1 - Out of memory error
3276
int pull_out_semijoin_tables(JOIN *join)
3279
List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);
3281
/* Try pulling out of the each of the semi-joins */
3282
while ((sj_nest= sj_list_it++))
3284
/* Action #1: Mark the constant tables to be pulled out */
3285
table_map pulled_tables= 0;
3287
List_iterator<TableList> child_li(sj_nest->nested_join->join_list);
3289
while ((tbl= child_li++))
3293
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
3294
if (tbl->table->map & join->const_table_map)
3296
pulled_tables |= tbl->table->map;
3302
Action #2: Find which tables we can pull out based on
3303
update_ref_and_keys() data. Note that pulling one table out can allow
3304
us to pull out some other tables too.
3306
bool pulled_a_table;
3309
pulled_a_table= false;
3311
while ((tbl= child_li++))
3313
if (tbl->table && !(pulled_tables & tbl->table->map))
3315
if (find_eq_ref_candidate(tbl->table,
3316
sj_nest->nested_join->used_tables &
3319
pulled_a_table= true;
3320
pulled_tables |= tbl->table->map;
3324
} while (pulled_a_table);
3327
if ((sj_nest)->nested_join->used_tables == pulled_tables)
3329
(sj_nest)->sj_inner_tables= 0;
3330
while ((tbl= child_li++))
3333
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3338
/* Record the bitmap of inner tables, mark the inner tables */
3339
table_map inner_tables=(sj_nest)->nested_join->used_tables &
3341
(sj_nest)->sj_inner_tables= inner_tables;
3342
while ((tbl= child_li++))
3346
if (inner_tables & tbl->table->map)
3347
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
3349
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
453
3357
/*****************************************************************************
454
Create JoinTableS, make a guess about the table types,
3358
Create JOIN_TABS, make a guess about the table types,
455
3359
Approximate how many records will be used in each table
456
3360
*****************************************************************************/
457
ha_rows get_quick_record_count(Session *session, optimizer::SqlSelect *select, Table *table, const key_map *keys,ha_rows limit)
3363
static ha_rows get_quick_record_count(THD *thd, SQL_SELECT *select,
3365
const key_map *keys,ha_rows limit)
460
if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))
3368
if (check_stack_overrun(thd, STACK_MIN_SIZE, NULL))
461
3369
return(0); // Fatal error flag is set
464
3372
select->head=table;
465
3373
table->reginfo.impossible_range=0;
466
if ((error= select->test_quick_select(session, *(key_map *)keys,(table_map) 0,
3374
if ((error= select->test_quick_select(thd, *(key_map *)keys,(table_map) 0,
467
3375
limit, 0, false)) == 1)
468
3376
return(select->quick->records);
469
3377
if (error == -1)
475
3383
return(HA_POS_ERROR); /* This shouldn't happend */
3387
This structure is used to collect info on potentially sargable
3388
predicates in order to check whether they become sargable after
3389
reading const tables.
3390
We form a bitmap of indexes that can be used for sargable predicates.
3391
Only such indexes are involved in range analysis.
3393
typedef struct st_sargable_param
3395
Field *field; /* field against which to check sargability */
3396
Item **arg_value; /* values of potential keys for lookups */
3397
uint32_t num_values; /* number of values in the above array */
3401
Calculate the best possible join and initialize the join structure.
3410
make_join_statistics(JOIN *join, TableList *tables, COND *conds,
3411
DYNAMIC_ARRAY *keyuse_array)
3415
uint32_t i,table_count,const_count,key;
3416
table_map found_const_table_map, all_table_map, found_ref, refs;
3417
key_map const_ref, eq_part;
3418
Table **table_vector;
3419
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
3420
KEYUSE *keyuse,*start_keyuse;
3421
table_map outer_join=0;
3422
SARGABLE_PARAM *sargables= 0;
3423
JOIN_TAB *stat_vector[MAX_TABLES+1];
3425
table_count=join->tables;
3426
stat=(JOIN_TAB*) join->thd->calloc(sizeof(JOIN_TAB)*table_count);
3427
stat_ref=(JOIN_TAB**) join->thd->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
3428
table_vector=(Table**) join->thd->alloc(sizeof(Table*)*(table_count*2));
3429
if (!stat || !stat_ref || !table_vector)
3430
return(1); // Eom /* purecov: inspected */
3432
join->best_ref=stat_vector;
3434
stat_end=stat+table_count;
3435
found_const_table_map= all_table_map=0;
3440
s++, tables= tables->next_leaf, i++)
3442
TableList *embedding= tables->embedding;
3445
s->const_keys.init();
3446
s->checked_keys.init();
3447
s->needed_reg.init();
3448
table_vector[i]=s->table=table=tables->table;
3449
table->pos_in_table_list= tables;
3450
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
3453
table->file->print_error(error, MYF(0));
3456
table->quick_keys.clear_all();
3457
table->reginfo.join_tab=s;
3458
table->reginfo.not_exists_optimize=0;
3459
memset(table->const_key_parts, 0,
3460
sizeof(key_part_map)*table->s->keys);
3461
all_table_map|= table->map;
3463
s->info=0; // For describe
3465
s->dependent= tables->dep_tables;
3466
s->key_dependent= 0;
3467
if (tables->schema_table)
3468
table->file->stats.records= 2;
3469
table->quick_condition_rows= table->file->stats.records;
3471
s->on_expr_ref= &tables->on_expr;
3472
if (*s->on_expr_ref)
3474
/* s is the only inner table of an outer join */
3475
if (!table->file->stats.records && !embedding)
3477
s->dependent= 0; // Ignore LEFT JOIN depend.
3478
set_position(join,const_count++,s,(KEYUSE*) 0);
3481
outer_join|= table->map;
3482
s->embedding_map= 0;
3483
for (;embedding; embedding= embedding->embedding)
3484
s->embedding_map|= embedding->nested_join->nj_map;
3487
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
3489
/* s belongs to a nested join, maybe to several embedded joins */
3490
s->embedding_map= 0;
3493
nested_join_st *nested_join= embedding->nested_join;
3494
s->embedding_map|=nested_join->nj_map;
3495
s->dependent|= embedding->dep_tables;
3496
embedding= embedding->embedding;
3497
outer_join|= nested_join->used_tables;
3502
if ((table->file->stats.records <= 1) &&
3504
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && !join->no_const_tables)
3506
set_position(join,const_count++,s,(KEYUSE*) 0);
3510
join->outer_join=outer_join;
3512
if (join->outer_join)
3515
Build transitive closure for relation 'to be dependent on'.
3516
This will speed up the plan search for many cases with outer joins,
3517
as well as allow us to catch illegal cross references/
3518
Warshall's algorithm is used to build the transitive closure.
3519
As we use bitmaps to represent the relation the complexity
3520
of the algorithm is O((number of tables)^2).
3522
for (i= 0, s= stat ; i < table_count ; i++, s++)
3524
for (uint32_t j= 0 ; j < table_count ; j++)
3526
table= stat[j].table;
3527
if (s->dependent & table->map)
3528
s->dependent |= table->reginfo.join_tab->dependent;
3531
s->table->maybe_null= 1;
3533
/* Catch illegal cross references for outer joins */
3534
for (i= 0, s= stat ; i < table_count ; i++, s++)
3536
if (s->dependent & s->table->map)
3538
join->tables=0; // Don't use join->table
3539
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
3542
s->key_dependent= s->dependent;
3546
if (conds || outer_join)
3547
if (update_ref_and_keys(join->thd, keyuse_array, stat, join->tables,
3548
conds, join->cond_equal,
3549
~outer_join, join->select_lex, &sargables))
3552
/* Read tables with 0 or 1 rows (system tables) */
3553
join->const_table_map= 0;
3555
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
3562
join->const_table_map|=s->table->map;
3563
if ((tmp=join_read_const_table(s, p_pos)))
3566
return(1); // Fatal error
3569
found_const_table_map|= s->table->map;
3572
/* loop until no more const tables are found */
3576
more_const_tables_found:
3581
We only have to loop from stat_vector + const_count as
3582
set_position() will move all const_tables first in stat_vector
3585
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
3590
If equi-join condition by a key is null rejecting and after a
3591
substitution of a const table the key value happens to be null
3592
then we can state that there are no matches for this equi-join.
3594
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
3597
When performing an outer join operation if there are no matching rows
3598
for the single row of the outer table all the inner tables are to be
3599
null complemented and thus considered as constant tables.
3600
Here we apply this consideration to the case of outer join operations
3601
with a single inner table only because the case with nested tables
3602
would require a more thorough analysis.
3603
TODO. Apply single row substitution to null complemented inner tables
3604
for nested outer join operations.
3606
while (keyuse->table == table)
3608
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
3609
keyuse->val->is_null() && keyuse->null_rejecting)
3612
mark_as_null_row(table);
3613
found_const_table_map|= table->map;
3614
join->const_table_map|= table->map;
3615
set_position(join,const_count++,s,(KEYUSE*) 0);
3616
goto more_const_tables_found;
3622
if (s->dependent) // If dependent on some table
3624
// All dep. must be constants
3625
if (s->dependent & ~(found_const_table_map))
3627
if (table->file->stats.records <= 1L &&
3628
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
3629
!table->pos_in_table_list->embedding)
3633
join->const_table_map|=table->map;
3634
set_position(join,const_count++,s,(KEYUSE*) 0);
3635
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
3638
return(1); // Fatal error
3641
found_const_table_map|= table->map;
3645
/* check if table can be read by key or table only uses const refs */
3646
if ((keyuse=s->keyuse))
3649
while (keyuse->table == table)
3651
start_keyuse=keyuse;
3653
s->keys.set_bit(key); // QQ: remove this ?
3656
const_ref.clear_all();
3657
eq_part.clear_all();
3660
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
3662
if (!((~found_const_table_map) & keyuse->used_tables))
3663
const_ref.set_bit(keyuse->keypart);
3665
refs|=keyuse->used_tables;
3666
eq_part.set_bit(keyuse->keypart);
3669
} while (keyuse->table == table && keyuse->key == key);
3671
if (eq_part.is_prefix(table->key_info[key].key_parts) &&
3672
!table->pos_in_table_list->embedding)
3674
if ((table->key_info[key].flags & (HA_NOSAME))
3677
if (const_ref == eq_part)
3678
{ // Found everything for ref.
3682
join->const_table_map|=table->map;
3683
set_position(join,const_count++,s,start_keyuse);
3684
if (create_ref_for_key(join, s, start_keyuse,
3685
found_const_table_map))
3687
if ((tmp=join_read_const_table(s,
3688
join->positions+const_count-1)))
3691
return(1); // Fatal error
3694
found_const_table_map|= table->map;
3698
found_ref|= refs; // Table is const if all refs are const
3700
else if (const_ref == eq_part)
3701
s->const_keys.set_bit(key);
3706
} while (join->const_table_map & found_ref && ref_changed);
3709
Update info on indexes that can be used for search lookups as
3710
reading const tables may has added new sargable predicates.
3712
if (const_count && sargables)
3714
for( ; sargables->field ; sargables++)
3716
Field *field= sargables->field;
3717
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
3718
key_map possible_keys= field->key_start;
3719
possible_keys.intersect(field->table->keys_in_use_for_query);
3721
for (uint32_t j=0; j < sargables->num_values; j++)
3722
is_const&= sargables->arg_value[j]->const_item();
3724
join_tab[0].const_keys.merge(possible_keys);
3728
if (pull_out_semijoin_tables(join))
3731
/* Calc how many (possible) matched records in each table */
3733
for (s=stat ; s < stat_end ; s++)
3735
if (s->type == JT_SYSTEM || s->type == JT_CONST)
3737
/* Only one matching row */
3738
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
3741
/* Approximate found rows and time to read them */
3742
s->found_records=s->records=s->table->file->stats.records;
3743
s->read_time=(ha_rows) s->table->file->scan_time();
3746
Set a max range of how many seeks we can expect when using keys
3747
This is can't be to high as otherwise we are likely to use
3750
s->worst_seeks= cmin((double) s->found_records / 10,
3751
(double) s->read_time*3);
3752
if (s->worst_seeks < 2.0) // Fix for small tables
3756
Add to stat->const_keys those indexes for which all group fields or
3757
all select distinct fields participate in one index.
3759
add_group_and_distinct_keys(join, s);
3761
if (!s->const_keys.is_clear_all() &&
3762
!s->table->pos_in_table_list->embedding)
3766
select= make_select(s->table, found_const_table_map,
3767
found_const_table_map,
3768
*s->on_expr_ref ? *s->on_expr_ref : conds,
3772
records= get_quick_record_count(join->thd, select, s->table,
3773
&s->const_keys, join->row_limit);
3774
s->quick=select->quick;
3775
s->needed_reg=select->needed_reg;
3777
if (records == 0 && s->table->reginfo.impossible_range)
3780
Impossible WHERE or ON expression
3781
In case of ON, we mark that the we match one empty NULL row.
3782
In case of WHERE, don't set found_const_table_map to get the
3783
caller to abort with a zero row result.
3785
join->const_table_map|= s->table->map;
3786
set_position(join,const_count++,s,(KEYUSE*) 0);
3788
if (*s->on_expr_ref)
3790
/* Generate empty row */
3791
s->info= "Impossible ON condition";
3792
found_const_table_map|= s->table->map;
3794
mark_as_null_row(s->table); // All fields are NULL
3797
if (records != HA_POS_ERROR)
3799
s->found_records=records;
3800
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
3806
join->join_tab=stat;
3807
join->map2table=stat_ref;
3808
join->table= join->all_tables=table_vector;
3809
join->const_tables=const_count;
3810
join->found_const_table_map=found_const_table_map;
3812
/* Find an optimal join order of the non-constant tables. */
3813
if (join->const_tables != join->tables)
3815
optimize_keyuse(join, keyuse_array);
3816
if (choose_plan(join, all_table_map & ~join->const_table_map))
3821
memcpy(join->best_positions, join->positions,
3822
sizeof(POSITION)*join->const_tables);
3823
join->best_read=1.0;
3825
/* Generate an execution plan from the found optimal join order. */
3826
return(join->thd->killed || get_best_combination(join));
478
3830
/*****************************************************************************
479
3831
Check with keys are used and with tables references with tables
480
3832
Updates in stat:
483
3835
keyuse Pointer to possible keys
484
3836
*****************************************************************************/
3838
/// Used when finding key fields
3839
typedef struct key_field_t {
3841
Item *val; ///< May be empty if diff constant
3843
uint optimize; // KEY_OPTIMIZE_*
3846
If true, the condition this struct represents will not be satisfied
3849
bool null_rejecting;
3850
bool *cond_guard; /* See KEYUSE::cond_guard */
3851
uint32_t sj_pred_no; /* See KEYUSE::sj_pred_no */
3855
Merge new key definitions to old ones, remove those not used in both.
3857
This is called for OR between different levels.
3859
To be able to do 'ref_or_null' we merge a comparison of a column
3860
and 'column IS NULL' to one test. This is useful for sub select queries
3861
that are internally transformed to something like:.
3864
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
3867
KEY_FIELD::null_rejecting is processed as follows: @n
3868
result has null_rejecting=true if it is set for both ORed references.
3870
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
3871
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
3874
The result of this is that we're missing some 'ref' accesses.
3875
OptimizerTeam: Fix this
3879
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
3882
if (start == new_fields)
3883
return start; // Impossible or
3884
if (new_fields == end)
3885
return start; // No new fields, skip all
3887
KEY_FIELD *first_free=new_fields;
3889
/* Mark all found fields in old array */
3890
for (; new_fields != end ; new_fields++)
3892
for (KEY_FIELD *old=start ; old != first_free ; old++)
3894
if (old->field == new_fields->field)
3897
NOTE: below const_item() call really works as "!used_tables()", i.e.
3898
it can return false where it is feasible to make it return true.
3900
The cause is as follows: Some of the tables are already known to be
3901
const tables (the detection code is in make_join_statistics(),
3902
above the update_ref_and_keys() call), but we didn't propagate
3903
information about this: Table::const_table is not set to true, and
3904
Item::update_used_tables() hasn't been called for each item.
3905
The result of this is that we're missing some 'ref' accesses.
3906
TODO: OptimizerTeam: Fix this
3908
if (!new_fields->val->const_item())
3911
If the value matches, we can use the key reference.
3912
If not, we keep it until we have examined all new values
3914
if (old->val->eq(new_fields->val, old->field->binary()))
3916
old->level= and_level;
3917
old->optimize= ((old->optimize & new_fields->optimize &
3918
KEY_OPTIMIZE_EXISTS) |
3919
((old->optimize | new_fields->optimize) &
3920
KEY_OPTIMIZE_REF_OR_NULL));
3921
old->null_rejecting= (old->null_rejecting &&
3922
new_fields->null_rejecting);
3925
else if (old->eq_func && new_fields->eq_func &&
3926
old->val->eq_by_collation(new_fields->val,
3927
old->field->binary(),
3928
old->field->charset()))
3931
old->level= and_level;
3932
old->optimize= ((old->optimize & new_fields->optimize &
3933
KEY_OPTIMIZE_EXISTS) |
3934
((old->optimize | new_fields->optimize) &
3935
KEY_OPTIMIZE_REF_OR_NULL));
3936
old->null_rejecting= (old->null_rejecting &&
3937
new_fields->null_rejecting);
3939
else if (old->eq_func && new_fields->eq_func &&
3940
((old->val->const_item() && old->val->is_null()) ||
3941
new_fields->val->is_null()))
3943
/* field = expression OR field IS NULL */
3944
old->level= and_level;
3945
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
3947
Remember the NOT NULL value unless the value does not depend
3950
if (!old->val->used_tables() && old->val->is_null())
3951
old->val= new_fields->val;
3952
/* The referred expression can be NULL: */
3953
old->null_rejecting= 0;
3958
We are comparing two different const. In this case we can't
3959
use a key-lookup on this so it's better to remove the value
3960
and let the range optimzier handle it
3962
if (old == --first_free) // If last item
3964
*old= *first_free; // Remove old value
3965
old--; // Retry this value
3970
/* Remove all not used items */
3971
for (KEY_FIELD *old=start ; old != first_free ;)
3973
if (old->level != and_level)
3974
{ // Not used in all levels
3975
if (old == --first_free)
3977
*old= *first_free; // Remove old value
3987
Add a possible key to array of possible keys if it's usable as a key
3989
@param key_fields Pointer to add key, if usable
3990
@param and_level And level, to be stored in KEY_FIELD
3991
@param cond Condition predicate
3992
@param field Field used in comparision
3993
@param eq_func True if we used =, <=> or IS NULL
3994
@param value Value used for comparison with field
3995
@param usable_tables Tables which can be used for key optimization
3996
@param sargables IN/OUT Array of found sargable candidates
3999
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
4000
table, we store this to be able to do not exists optimization later.
4003
*key_fields is incremented if we stored a key in the array
4007
add_key_field(KEY_FIELD **key_fields,uint32_t and_level, Item_func *cond,
4008
Field *field, bool eq_func, Item **value, uint32_t num_values,
4009
table_map usable_tables, SARGABLE_PARAM **sargables)
4011
uint32_t exists_optimize= 0;
4012
if (!(field->flags & PART_KEY_FLAG))
4014
// Don't remove column IS NULL on a LEFT JOIN table
4015
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4016
!field->table->maybe_null || field->null_ptr)
4017
return; // Not a key. Skip it
4018
exists_optimize= KEY_OPTIMIZE_EXISTS;
4019
assert(num_values == 1);
4023
table_map used_tables=0;
4025
for (uint32_t i=0; i<num_values; i++)
4027
used_tables|=(value[i])->used_tables();
4028
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
4033
if (!(usable_tables & field->table->map))
4035
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4036
!field->table->maybe_null || field->null_ptr)
4037
return; // Can't use left join optimize
4038
exists_optimize= KEY_OPTIMIZE_EXISTS;
4042
JOIN_TAB *stat=field->table->reginfo.join_tab;
4043
key_map possible_keys=field->key_start;
4044
possible_keys.intersect(field->table->keys_in_use_for_query);
4045
stat[0].keys.merge(possible_keys); // Add possible keys
4048
Save the following cases:
4050
Field LIKE constant where constant doesn't start with a wildcard
4051
Field = field2 where field2 is in a different table
4058
stat[0].key_dependent|=used_tables;
4061
for (uint32_t i=0; i<num_values; i++)
4063
if (!(is_const&= value[i]->const_item()))
4067
stat[0].const_keys.merge(possible_keys);
4071
Save info to be able check whether this predicate can be
4072
considered as sargable for range analisis after reading const tables.
4073
We do not save info about equalities as update_const_equal_items
4074
will take care of updating info on keys from sargable equalities.
4077
(*sargables)->field= field;
4078
(*sargables)->arg_value= value;
4079
(*sargables)->num_values= num_values;
4082
We can't always use indexes when comparing a string index to a
4083
number. cmp_type() is checked to allow compare of dates to numbers.
4084
eq_func is NEVER true when num_values > 1
4089
Additional optimization: if we're processing
4090
"t.key BETWEEN c1 AND c1" then proceed as if we were processing
4092
TODO: This is a very limited fix. A more generic fix is possible.
4093
There are 2 options:
4094
A) Make equality propagation code be able to handle BETWEEN
4095
(including cases like t1.key BETWEEN t2.key AND t3.key)
4096
B) Make range optimizer to infer additional "t.key = c" equalities
4097
and use them in equality propagation process (see details in
4100
if ((cond->functype() != Item_func::BETWEEN) ||
4101
((Item_func_between*) cond)->negated ||
4102
!value[0]->eq(value[1], field->binary()))
4107
if (field->result_type() == STRING_RESULT)
4109
if ((*value)->result_type() != STRING_RESULT)
4111
if (field->cmp_type() != (*value)->result_type())
4117
We can't use indexes if the effective collation
4118
of the operation differ from the field collation.
4120
if (field->cmp_type() == STRING_RESULT &&
4121
((Field_str*)field)->charset() != cond->compare_collation())
4128
For the moment eq_func is always true. This slot is reserved for future
4129
extensions where we want to remembers other things than just eq comparisons
4132
/* Store possible eq field */
4133
(*key_fields)->field= field;
4134
(*key_fields)->eq_func= eq_func;
4135
(*key_fields)->val= *value;
4136
(*key_fields)->level= and_level;
4137
(*key_fields)->optimize= exists_optimize;
4139
If the condition has form "tbl.keypart = othertbl.field" and
4140
othertbl.field can be NULL, there will be no matches if othertbl.field
4142
We use null_rejecting in add_not_null_conds() to add
4143
'othertbl.field IS NOT NULL' to tab->select_cond.
4145
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
4146
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
4147
((*value)->type() == Item::FIELD_ITEM) &&
4148
((Item_field*)*value)->field->maybe_null());
4149
(*key_fields)->cond_guard= NULL;
4150
(*key_fields)->sj_pred_no= (cond->name >= subq_sj_cond_name &&
4151
cond->name < subq_sj_cond_name + 64)?
4152
cond->name - subq_sj_cond_name: UINT_MAX;
4157
Add possible keys to array of possible keys originated from a simple
4160
@param key_fields Pointer to add key, if usable
4161
@param and_level And level, to be stored in KEY_FIELD
4162
@param cond Condition predicate
4163
@param field Field used in comparision
4164
@param eq_func True if we used =, <=> or IS NULL
4165
@param value Value used for comparison with field
4166
Is NULL for BETWEEN and IN
4167
@param usable_tables Tables which can be used for key optimization
4168
@param sargables IN/OUT Array of found sargable candidates
4171
If field items f1 and f2 belong to the same multiple equality and
4172
a key is added for f1, the the same key is added for f2.
4175
*key_fields is incremented if we stored a key in the array
4179
add_key_equal_fields(KEY_FIELD **key_fields, uint32_t and_level,
4180
Item_func *cond, Item_field *field_item,
4181
bool eq_func, Item **val,
4182
uint32_t num_values, table_map usable_tables,
4183
SARGABLE_PARAM **sargables)
4185
Field *field= field_item->field;
4186
add_key_field(key_fields, and_level, cond, field,
4187
eq_func, val, num_values, usable_tables, sargables);
4188
Item_equal *item_equal= field_item->item_equal;
4192
Add to the set of possible key values every substitution of
4193
the field for an equal field included into item_equal
4195
Item_equal_iterator it(*item_equal);
4197
while ((item= it++))
4199
if (!field->eq(item->field))
4201
add_key_field(key_fields, and_level, cond, item->field,
4202
eq_func, val, num_values, usable_tables,
4210
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint32_t *and_level,
4211
COND *cond, table_map usable_tables,
4212
SARGABLE_PARAM **sargables)
4214
if (cond->type() == Item_func::COND_ITEM)
4216
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
4217
KEY_FIELD *org_key_fields= *key_fields;
4219
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
4223
add_key_fields(join, key_fields, and_level, item, usable_tables,
4225
for (; org_key_fields != *key_fields ; org_key_fields++)
4226
org_key_fields->level= *and_level;
4231
add_key_fields(join, key_fields, and_level, li++, usable_tables,
4236
KEY_FIELD *start_key_fields= *key_fields;
4238
add_key_fields(join, key_fields, and_level, item, usable_tables,
4240
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
4241
*key_fields,++(*and_level));
4248
Subquery optimization: Conditions that are pushed down into subqueries
4249
are wrapped into Item_func_trig_cond. We process the wrapped condition
4250
but need to set cond_guard for KEYUSE elements generated from it.
4253
if (cond->type() == Item::FUNC_ITEM &&
4254
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
4256
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
4257
if (!join->group_list && !join->order &&
4259
join->unit->item->substype() == Item_subselect::IN_SUBS &&
4260
!join->unit->is_union())
4262
KEY_FIELD *save= *key_fields;
4263
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
4265
// Indicate that this ref access candidate is for subquery lookup:
4266
for (; save != *key_fields; save++)
4267
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
4273
/* If item is of type 'field op field/constant' add it to key_fields */
4274
if (cond->type() != Item::FUNC_ITEM)
4276
Item_func *cond_func= (Item_func*) cond;
4277
switch (cond_func->select_optimize()) {
4278
case Item_func::OPTIMIZE_NONE:
4280
case Item_func::OPTIMIZE_KEY:
4284
if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
4285
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4287
values= cond_func->arguments()+1;
4288
if (cond_func->functype() == Item_func::NE_FUNC &&
4289
cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4290
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4292
assert(cond_func->functype() != Item_func::IN_FUNC ||
4293
cond_func->argument_count() != 2);
4294
add_key_equal_fields(key_fields, *and_level, cond_func,
4295
(Item_field*) (cond_func->key_item()->real_item()),
4297
cond_func->argument_count()-1,
4298
usable_tables, sargables);
4300
if (cond_func->functype() == Item_func::BETWEEN)
4302
values= cond_func->arguments();
4303
for (uint32_t i= 1 ; i < cond_func->argument_count() ; i++)
4305
Item_field *field_item;
4306
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
4308
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
4310
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
4311
add_key_equal_fields(key_fields, *and_level, cond_func,
4312
field_item, 0, values, 1, usable_tables,
4319
case Item_func::OPTIMIZE_OP:
4321
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
4322
cond_func->functype() == Item_func::EQUAL_FUNC);
4324
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4325
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4327
add_key_equal_fields(key_fields, *and_level, cond_func,
4328
(Item_field*) (cond_func->arguments()[0])->real_item(),
4330
cond_func->arguments()+1, 1, usable_tables,
4333
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4334
cond_func->functype() != Item_func::LIKE_FUNC &&
4335
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
4337
add_key_equal_fields(key_fields, *and_level, cond_func,
4338
(Item_field*) (cond_func->arguments()[1])->real_item(),
4340
cond_func->arguments(),1,usable_tables,
4345
case Item_func::OPTIMIZE_NULL:
4346
/* column_name IS [NOT] NULL */
4347
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4348
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4350
Item *tmp=new Item_null;
4351
if (unlikely(!tmp)) // Should never be true
4353
add_key_equal_fields(key_fields, *and_level, cond_func,
4354
(Item_field*) (cond_func->arguments()[0])->real_item(),
4355
cond_func->functype() == Item_func::ISNULL_FUNC,
4356
&tmp, 1, usable_tables, sargables);
4359
case Item_func::OPTIMIZE_EQUAL:
4360
Item_equal *item_equal= (Item_equal *) cond;
4361
Item *const_item= item_equal->get_const();
4362
Item_equal_iterator it(*item_equal);
4367
For each field field1 from item_equal consider the equality
4368
field1=const_item as a condition allowing an index access of the table
4369
with field1 by the keys value of field1.
4371
while ((item= it++))
4373
add_key_field(key_fields, *and_level, cond_func, item->field,
4374
true, &const_item, 1, usable_tables, sargables);
4380
Consider all pairs of different fields included into item_equal.
4381
For each of them (field1, field1) consider the equality
4382
field1=field2 as a condition allowing an index access of the table
4383
with field1 by the keys value of field2.
4385
Item_equal_iterator fi(*item_equal);
4386
while ((item= fi++))
4388
Field *field= item->field;
4389
while ((item= it++))
4391
if (!field->eq(item->field))
4393
add_key_field(key_fields, *and_level, cond_func, field,
4394
true, (Item **) &item, 1, usable_tables,
488
4406
Add all keys with uses 'field' for some keypart.
490
4408
If field->and_level != and_level then only mark key_part as const_part.
492
uint32_t max_part_bit(key_part_map bits)
4412
max_part_bit(key_part_map bits)
495
4415
for (found=0; bits & 1 ; found++,bits>>=1) ;
499
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)
4420
add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
4422
Field *field=key_field->field;
4423
Table *form= field->table;
4426
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
4428
for (uint32_t key= 0 ; key < form->sizeKeys() ; key++)
4430
if (!(form->keys_in_use_for_query.is_set(key)))
4433
uint32_t key_parts= (uint) form->key_info[key].key_parts;
4434
for (uint32_t part=0 ; part < key_parts ; part++)
4436
if (field->eq(form->key_info[key].key_part[part].field))
4438
keyuse.table= field->table;
4439
keyuse.val = key_field->val;
4441
keyuse.keypart=part;
4442
keyuse.keypart_map= (key_part_map) 1 << part;
4443
keyuse.used_tables=key_field->val->used_tables();
4444
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
4445
keyuse.null_rejecting= key_field->null_rejecting;
4446
keyuse.cond_guard= key_field->cond_guard;
4447
keyuse.sj_pred_no= key_field->sj_pred_no;
4448
insert_dynamic(keyuse_array,(unsigned char*) &keyuse);
4456
sort_keyuse(KEYUSE *a,KEYUSE *b)
502
if (a->getTable()->tablenr != b->getTable()->tablenr)
503
return static_cast<int>((a->getTable()->tablenr - b->getTable()->tablenr));
504
if (a->getKey() != b->getKey())
505
return static_cast<int>((a->getKey() - b->getKey()));
506
if (a->getKeypart() != b->getKeypart())
507
return static_cast<int>((a->getKeypart() - b->getKeypart()));
4459
if (a->table->tablenr != b->table->tablenr)
4460
return (int) (a->table->tablenr - b->table->tablenr);
4461
if (a->key != b->key)
4462
return (int) (a->key - b->key);
4463
if (a->keypart != b->keypart)
4464
return (int) (a->keypart - b->keypart);
508
4465
// Place const values before other ones
509
if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -
510
test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))
4466
if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
4467
test((b->used_tables & ~OUTER_REF_TABLE_BIT))))
512
4469
/* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
513
return static_cast<int>(((a->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) -
514
(b->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)));
4470
return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
4471
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
4476
Add to KEY_FIELD array all 'ref' access candidates within nested join.
4478
This function populates KEY_FIELD array with entries generated from the
4479
ON condition of the given nested join, and does the same for nested joins
4480
contained within this nested join.
4482
@param[in] nested_join_table Nested join pseudo-table to process
4483
@param[in,out] end End of the key field array
4484
@param[in,out] and_level And-level
4485
@param[in,out] sargables Array of found sargable candidates
4489
We can add accesses to the tables that are direct children of this nested
4490
join (1), and are not inner tables w.r.t their neighbours (2).
4492
Example for #1 (outer brackets pair denotes nested join this function is
4495
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
4499
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
4501
In examples 1-2 for condition cond, we can add 'ref' access candidates to
4505
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
4507
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
4510
static void add_key_fields_for_nj(JOIN *join, TableList *nested_join_table,
4511
KEY_FIELD **end, uint32_t *and_level,
4512
SARGABLE_PARAM **sargables)
4514
List_iterator<TableList> li(nested_join_table->nested_join->join_list);
4515
List_iterator<TableList> li2(nested_join_table->nested_join->join_list);
4516
bool have_another = false;
4517
table_map tables= 0;
4519
assert(nested_join_table->nested_join);
4521
while ((table= li++) || (have_another && (li=li2, have_another=false,
4524
if (table->nested_join)
4526
if (!table->on_expr)
4528
/* It's a semi-join nest. Walk into it as if it wasn't a nest */
4531
li= List_iterator<TableList>(table->nested_join->join_list);
4534
add_key_fields_for_nj(join, table, end, and_level, sargables);
4537
if (!table->on_expr)
4538
tables |= table->table->map;
4540
if (nested_join_table->on_expr)
4541
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
519
4547
Update keyuse array with all possible keys we can use to fetch rows.
522
@param[out] keyuse Put here ordered array of KeyUse structures
4550
@param[out] keyuse Put here ordered array of KEYUSE structures
523
4551
@param join_tab Array in tablenr_order
524
4552
@param tables Number of tables in join
525
4553
@param cond WHERE condition (note that the function analyzes
774
4806
/* Intersect the keys of all group fields. */
775
4807
cur_item= indexed_fields_it++;
776
possible_keys|= cur_item->field->part_of_key;
4808
possible_keys.merge(cur_item->field->part_of_key);
777
4809
while ((cur_item= indexed_fields_it++))
779
possible_keys&= cur_item->field->part_of_key;
782
if (possible_keys.any())
783
join_tab->const_keys|= possible_keys;
787
Compare two JoinTable objects based on the number of accessed records.
789
@param ptr1 pointer to first JoinTable object
790
@param ptr2 pointer to second JoinTable object
4811
possible_keys.intersect(cur_item->field->part_of_key);
4814
if (!possible_keys.is_clear_all())
4815
join_tab->const_keys.merge(possible_keys);
4819
/*****************************************************************************
4820
Go through all combinations of not marked tables and find the one
4821
which uses least records
4822
*****************************************************************************/
4824
/** Save const tables first as used tables. */
4827
set_position(JOIN *join,uint32_t idx,JOIN_TAB *table,KEYUSE *key)
4829
join->positions[idx].table= table;
4830
join->positions[idx].key=key;
4831
join->positions[idx].records_read=1.0; /* This is a const table */
4832
join->positions[idx].ref_depend_map= 0;
4834
/* Move the const table as down as possible in best_ref */
4835
JOIN_TAB **pos=join->best_ref+idx+1;
4836
JOIN_TAB *next=join->best_ref[idx];
4837
for (;next != table ; pos++)
4839
JOIN_TAB *tmp=pos[0];
4843
join->best_ref[idx]=table;
4848
Given a semi-join nest, find out which of the IN-equalities are bound
4851
get_bound_sj_equalities()
4852
sj_nest Semi-join nest
4853
remaining_tables Tables that are not yet bound
4856
Given a semi-join nest, find out which of the IN-equalities have their
4857
left part expression bound (i.e. the said expression doesn't refer to
4858
any of remaining_tables and can be evaluated).
4861
Bitmap of bound IN-equalities.
4864
uint64_t get_bound_sj_equalities(TableList *sj_nest,
4865
table_map remaining_tables)
4867
List_iterator<Item> li(sj_nest->nested_join->sj_outer_expr_list);
4871
while ((item= li++))
4874
Q: should this take into account equality propagation and how?
4875
A: If e->outer_side is an Item_field, walk over the equality
4876
class and see if there is an element that is bound?
4877
(this is an optional feature)
4879
if (!(item->used_tables() & remaining_tables))
4889
Find the best access path for an extension of a partial execution
4890
plan and add this path to the plan.
4892
The function finds the best access path to table 's' from the passed
4893
partial plan where an access path is the general term for any means to
4894
access the data in 's'. An access path may use either an index or a scan,
4895
whichever is cheaper. The input partial plan is passed via the array
4896
'join->positions' of length 'idx'. The chosen access method for 's' and its
4897
cost are stored in 'join->positions[idx]'.
4899
@param join pointer to the structure providing all context info
4901
@param s the table to be joined by the function
4902
@param thd thread for the connection that submitted the query
4903
@param remaining_tables set of tables not included into the partial plan yet
4904
@param idx the length of the partial plan
4905
@param record_count estimate for the number of records returned by the
4907
@param read_time the cost of the partial plan
4914
best_access_path(JOIN *join,
4917
table_map remaining_tables,
4919
double record_count,
4920
double read_time __attribute__((unused)))
4922
KEYUSE *best_key= 0;
4923
uint32_t best_max_key_part= 0;
4924
bool found_constraint= 0;
4925
double best= DBL_MAX;
4926
double best_time= DBL_MAX;
4927
double records= DBL_MAX;
4928
table_map best_ref_depends_map= 0;
4931
uint32_t best_is_sj_inside_out= 0;
4934
{ /* Use key if possible */
4935
Table *table= s->table;
4936
KEYUSE *keyuse,*start_key=0;
4937
double best_records= DBL_MAX;
4938
uint32_t max_key_part=0;
4939
uint64_t bound_sj_equalities= 0;
4940
bool try_sj_inside_out= false;
4942
Discover the bound equalites. We need to do this, if
4943
1. The next table is an SJ-inner table, and
4944
2. It is the first table from that semijoin, and
4945
3. We're not within a semi-join range (i.e. all semi-joins either have
4946
all or none of their tables in join_table_map), except
4947
s->emb_sj_nest (which we've just entered).
4948
3. All correlation references from this sj-nest are bound
4950
if (s->emb_sj_nest && // (1)
4951
s->emb_sj_nest->sj_in_exprs < 64 &&
4952
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
4953
s->emb_sj_nest->sj_inner_tables) && // (2)
4954
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
4955
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
4957
/* This table is an InsideOut scan candidate */
4958
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
4960
try_sj_inside_out= true;
4963
/* Test how we can use keys */
4964
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
4965
for (keyuse=s->keyuse ; keyuse->table == table ;)
4967
key_part_map found_part= 0;
4968
table_map found_ref= 0;
4969
uint32_t key= keyuse->key;
4970
KEY *keyinfo= table->key_info+key;
4971
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
4972
key_part_map const_part= 0;
4973
/* The or-null keypart in ref-or-null access: */
4974
key_part_map ref_or_null_part= 0;
4976
/* Calculate how many key segments of the current key we can use */
4978
uint64_t handled_sj_equalities=0;
4979
key_part_map sj_insideout_map= 0;
4981
do /* For each keypart */
4983
uint32_t keypart= keyuse->keypart;
4984
table_map best_part_found_ref= 0;
4985
double best_prev_record_reads= DBL_MAX;
4987
do /* For each way to access the keypart */
4991
if 1. expression doesn't refer to forward tables
4992
2. we won't get two ref-or-null's
4994
if (!(remaining_tables & keyuse->used_tables) &&
4995
!(ref_or_null_part && (keyuse->optimize &
4996
KEY_OPTIMIZE_REF_OR_NULL)))
4998
found_part|= keyuse->keypart_map;
4999
if (!(keyuse->used_tables & ~join->const_table_map))
5000
const_part|= keyuse->keypart_map;
5002
double tmp2= prev_record_reads(join, idx, (found_ref |
5003
keyuse->used_tables));
5004
if (tmp2 < best_prev_record_reads)
5006
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
5007
best_prev_record_reads= tmp2;
5009
if (rec > keyuse->ref_table_rows)
5010
rec= keyuse->ref_table_rows;
5012
If there is one 'key_column IS NULL' expression, we can
5013
use this ref_or_null optimisation of this field
5015
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
5016
ref_or_null_part |= keyuse->keypart_map;
5019
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
5021
if (!(remaining_tables & keyuse->used_tables))
5022
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
5025
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
5026
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
5031
} while (keyuse->table == table && keyuse->key == key &&
5032
keyuse->keypart == keypart);
5033
found_ref|= best_part_found_ref;
5034
} while (keyuse->table == table && keyuse->key == key);
5037
Assume that that each key matches a proportional part of table.
5039
if (!found_part && !handled_sj_equalities)
5040
continue; // Nothing usable found
5042
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
5043
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
5045
bool sj_inside_out_scan= false;
5047
found_constraint= 1;
5049
Check if InsideOut scan is applicable:
5050
1. All IN-equalities are either "bound" or "handled"
5051
2. Index keyparts are
5054
if (try_sj_inside_out &&
5055
table->covering_keys.is_set(key) &&
5056
(handled_sj_equalities | bound_sj_equalities) == // (1)
5057
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
5059
uint32_t n_fixed_parts= max_part_bit(found_part);
5060
if (n_fixed_parts != keyinfo->key_parts &&
5061
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
5062
PREV_BITS(uint, keyinfo->key_parts))
5065
Not all parts are fixed. Produce bitmap of remaining bits and
5066
check if all of them are covered.
5068
sj_inside_out_scan= true;
5072
It's a confluent ref scan.
5074
That is, all found KEYUSE elements refer to IN-equalities,
5075
and there is really no ref access because there is no
5076
t.keypart0 = {bound expression}
5078
Calculate the cost of complete loose index scan.
5080
records= (double)s->table->file->stats.records;
5082
/* The cost is entire index scan cost (divided by 2) */
5083
best_time= s->table->file->index_only_read_time(key, records);
5085
/* Now figure how many different keys we will get */
5087
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
5088
records= records / rpc;
5095
Check if we found full key
5097
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
5100
max_key_part= UINT32_MAX;
5101
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
5103
tmp = prev_record_reads(join, idx, found_ref);
5109
{ /* We found a const key */
5111
ReuseRangeEstimateForRef-1:
5112
We get here if we've found a ref(const) (c_i are constants):
5113
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
5115
If range optimizer was able to construct a "range"
5116
access on this index, then its condition "quick_cond" was
5117
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
5118
from the range optimizer.
5120
Proof of (*): By properties of range and ref optimizers
5121
quick_cond will be equal or tighther than ref_const_cond.
5122
ref_const_cond already covers "smallest" possible interval -
5123
a singlepoint interval over all keyparts. Therefore,
5124
quick_cond is equivalent to ref_const_cond (if it was an
5125
empty interval we wouldn't have got here).
5127
if (table->quick_keys.is_set(key))
5128
records= (double) table->quick_rows[key];
5131
/* quick_range couldn't use key! */
5132
records= (double) s->records/rec;
5137
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
5138
{ /* Prefer longer keys */
5140
((double) s->records / (double) rec *
5142
((double) (table->s->max_key_length-keyinfo->key_length) /
5143
(double) table->s->max_key_length)));
5145
records=2.0; /* Can't be as good as a unique */
5148
ReuseRangeEstimateForRef-2: We get here if we could not reuse
5149
E(#rows) from range optimizer. Make another try:
5151
If range optimizer produced E(#rows) for a prefix of the ref
5152
access we're considering, and that E(#rows) is lower then our
5153
current estimate, make an adjustment. The criteria of when we
5154
can make an adjustment is a special case of the criteria used
5155
in ReuseRangeEstimateForRef-3.
5157
if (table->quick_keys.is_set(key) &&
5158
const_part & (1 << table->quick_key_parts[key]) &&
5159
table->quick_n_ranges[key] == 1 &&
5160
records > (double) table->quick_rows[key])
5162
records= (double) table->quick_rows[key];
5165
/* Limit the number of matched rows */
5167
set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key);
5168
if (table->covering_keys.is_set(key))
5170
/* we can use only index tree */
5171
tmp= record_count * table->file->index_only_read_time(key, tmp);
5174
tmp= record_count*cmin(tmp,s->worst_seeks);
5180
Use as much key-parts as possible and a uniq key is better
5181
than a not unique key
5182
Set tmp to (previous record count) * (records / combination)
5184
if ((found_part & 1) &&
5185
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
5186
found_part == PREV_BITS(uint,keyinfo->key_parts)))
5188
max_key_part= max_part_bit(found_part);
5190
ReuseRangeEstimateForRef-3:
5191
We're now considering a ref[or_null] access via
5192
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
5193
(same-as-above but with one cond replaced
5194
with "t.keypart_i IS NULL")] (**)
5196
Try re-using E(#rows) from "range" optimizer:
5197
We can do so if "range" optimizer used the same intervals as
5198
in (**). The intervals used by range optimizer may be not
5199
available at this point (as "range" access might have choosen to
5200
create quick select over another index), so we can't compare
5201
them to (**). We'll make indirect judgements instead.
5202
The sufficient conditions for re-use are:
5203
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
5204
this is not satisfied we have no way to know which ranges
5205
will be actually scanned by 'ref' until we execute the
5207
(C2) max #key parts in 'range' access == K == max_key_part (this
5208
is apparently a necessary requirement)
5210
We also have a property that "range optimizer produces equal or
5211
tighter set of scan intervals than ref(const) optimizer". Each
5212
of the intervals in (**) are "tightest possible" intervals when
5213
one limits itself to using keyparts 1..K (which we do in #2).
5214
From here it follows that range access used either one, or
5215
both of the (I1) and (I2) intervals:
5217
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
5218
(same-as-above but with one cond replaced
5219
with "t.keypart_i IS NULL") (I2)
5221
The remaining part is to exclude the situation where range
5222
optimizer used one interval while we're considering
5223
ref-or-null and looking for estimate for two intervals. This
5224
is done by last limitation:
5226
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
5228
if (table->quick_keys.is_set(key) && !found_ref && //(C1)
5229
table->quick_key_parts[key] == max_key_part && //(C2)
5230
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
5232
tmp= records= (double) table->quick_rows[key];
5236
/* Check if we have statistic about the distribution */
5237
if ((records= keyinfo->rec_per_key[max_key_part-1]))
5240
Fix for the case where the index statistics is too
5242
(1) We're considering ref(const) and there is quick select
5244
(2) and that quick select uses more keyparts (i.e. it will
5245
scan equal/smaller interval then this ref(const))
5246
(3) and E(#rows) for quick select is higher then our
5249
We'll use E(#rows) from quick select.
5251
Q: Why do we choose to use 'ref'? Won't quick select be
5252
cheaper in some cases ?
5253
TODO: figure this out and adjust the plan choice if needed.
5255
if (!found_ref && table->quick_keys.is_set(key) && // (1)
5256
table->quick_key_parts[key] > max_key_part && // (2)
5257
records < (double)table->quick_rows[key]) // (3)
5258
records= (double)table->quick_rows[key];
5265
Assume that the first key part matches 1% of the file
5266
and that the whole key matches 10 (duplicates) or 1
5268
Assume also that more key matches proportionally more
5270
This gives the formula:
5271
records = (x * (b-a) + a*c-b)/(c-1)
5273
b = records matched by whole key
5274
a = records matched by first key part (1% of all records?)
5275
c = number of key parts in key
5276
x = used key parts (1 <= x <= c)
5279
if (!(rec_per_key=(double)
5280
keyinfo->rec_per_key[keyinfo->key_parts-1]))
5281
rec_per_key=(double) s->records/rec+1;
5285
else if (rec_per_key/(double) s->records >= 0.01)
5289
double a=s->records*0.01;
5290
if (keyinfo->key_parts > 1)
5291
tmp= (max_key_part * (rec_per_key - a) +
5292
a*keyinfo->key_parts - rec_per_key)/
5293
(keyinfo->key_parts-1);
5296
set_if_bigger(tmp,1.0);
5298
records = (ulong) tmp;
5301
if (ref_or_null_part)
5303
/* We need to do two key searches to find key */
5309
ReuseRangeEstimateForRef-4: We get here if we could not reuse
5310
E(#rows) from range optimizer. Make another try:
5312
If range optimizer produced E(#rows) for a prefix of the ref
5313
access we're considering, and that E(#rows) is lower then our
5314
current estimate, make the adjustment.
5316
The decision whether we can re-use the estimate from the range
5317
optimizer is the same as in ReuseRangeEstimateForRef-3,
5318
applied to first table->quick_key_parts[key] key parts.
5320
if (table->quick_keys.is_set(key) &&
5321
table->quick_key_parts[key] <= max_key_part &&
5322
const_part & (1 << table->quick_key_parts[key]) &&
5323
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
5324
const_part) ? 1 : 0) &&
5325
records > (double) table->quick_rows[key])
5327
tmp= records= (double) table->quick_rows[key];
5331
/* Limit the number of matched rows */
5332
set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key);
5333
if (table->covering_keys.is_set(key))
5335
/* we can use only index tree */
5336
tmp= record_count * table->file->index_only_read_time(key, tmp);
5339
tmp= record_count * cmin(tmp,s->worst_seeks);
5342
tmp= best_time; // Do nothing
5345
if (sj_inside_out_scan && !start_key)
5353
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
5355
best_time= tmp + records/(double) TIME_FOR_COMPARE;
5357
best_records= records;
5358
best_key= start_key;
5359
best_max_key_part= max_key_part;
5360
best_ref_depends_map= found_ref;
5361
best_is_sj_inside_out= sj_inside_out_scan;
5364
records= best_records;
5368
Don't test table scan if it can't be better.
5369
Prefer key lookup if we would use the same key for scanning.
5371
Don't do a table scan on InnoDB tables, if we can read the used
5372
parts of the row from any of the used index.
5373
This is because table scans uses index and we would not win
5374
anything by using a table scan.
5376
A word for word translation of the below if-statement in sergefp's
5377
understanding: we check if we should use table scan if:
5378
(1) The found 'ref' access produces more records than a table scan
5379
(or index scan, or quick select), or 'ref' is more expensive than
5381
(2) This doesn't hold: the best way to perform table scan is to to perform
5382
'range' access using index IDX, and the best way to perform 'ref'
5383
access is to use the same index IDX, with the same or more key parts.
5384
(note: it is not clear how this rule is/should be extended to
5385
index_merge quick selects)
5386
(3) See above note about InnoDB.
5387
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
5388
path, but there is no quick select)
5389
If the condition in the above brackets holds, then the only possible
5390
"table scan" access method is ALL/index (there is no quick select).
5391
Since we have a 'ref' access path, and FORCE INDEX instructs us to
5392
choose it over ALL/index, there is no need to consider a full table
5395
if ((records >= s->found_records || best > s->read_time) && // (1)
5396
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
5397
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
5398
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
5399
! s->table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
5400
!(s->table->force_index && best_key && !s->quick)) // (4)
5401
{ // Check full join
5402
ha_rows rnd_records= s->found_records;
5404
If there is a filtering condition on the table (i.e. ref analyzer found
5405
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
5406
preceding this table in the join order we're now considering), then
5407
assume that 25% of the rows will be filtered out by this condition.
5409
This heuristic is supposed to force tables used in exprZ to be before
5410
this table in join order.
5412
if (found_constraint)
5413
rnd_records-= rnd_records/4;
5416
If applicable, get a more accurate estimate. Don't use the two
5419
if (s->table->quick_condition_rows != s->found_records)
5420
rnd_records= s->table->quick_condition_rows;
5423
Range optimizer never proposes a RANGE if it isn't better
5424
than FULL: so if RANGE is present, it's always preferred to FULL.
5425
Here we estimate its cost.
5431
- read record range through 'quick'
5432
- skip rows which does not satisfy WHERE constraints
5434
We take into account possible use of join cache for ALL/index
5435
access (see first else-branch below), but we don't take it into
5436
account here for range/index_merge access. Find out why this is so.
5439
(s->quick->read_time +
5440
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
5444
/* Estimate cost of reading table. */
5445
tmp= s->table->file->scan_time();
5446
if (s->table->map & join->outer_join) // Can't use join cache
5449
For each record we have to:
5450
- read the whole table record
5451
- skip rows which does not satisfy join condition
5455
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
5459
/* We read the table as many times as join buffer becomes full. */
5460
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
5462
(double) thd->variables.join_buff_size));
5464
We don't make full cartesian product between rows in the scanned
5465
table and existing records because we skip all rows from the
5466
scanned table, which does not satisfy join condition when
5467
we read the table (see flush_cached_records for details). Here we
5468
take into account cost to read and skip these records.
5470
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
5475
We estimate the cost of evaluating WHERE clause for found records
5476
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
5477
tmp give us total cost of using Table SCAN
5479
if (best == DBL_MAX ||
5480
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
5481
best + record_count/(double) TIME_FOR_COMPARE*records))
5484
If the table has a range (s->quick is set) make_join_select()
5485
will ensure that this will be used
5488
records= rows2double(rnd_records);
5490
/* range/index_merge/ALL/index access method are "independent", so: */
5491
best_ref_depends_map= 0;
5492
best_is_sj_inside_out= false;
5496
/* Update the cost information for the current partial plan */
5497
join->positions[idx].records_read= records;
5498
join->positions[idx].read_time= best;
5499
join->positions[idx].key= best_key;
5500
join->positions[idx].table= s;
5501
join->positions[idx].ref_depend_map= best_ref_depends_map;
5502
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
5505
idx == join->const_tables &&
5506
s->table == join->sort_by_table &&
5507
join->unit->select_limit_cnt >= records)
5508
join->sort_by_table= (Table*) 1; // Must use temporary table
5515
Selects and invokes a search strategy for an optimal query plan.
5517
The function checks user-configurable parameters that control the search
5518
strategy for an optimal plan, selects the search method and then invokes
5519
it. Each specific optimization procedure stores the final optimal plan in
5520
the array 'join->best_positions', and the cost of the plan in
5523
@param join pointer to the structure providing all context info for
5525
@param join_tables set of the tables in the query
5528
'MAX_TABLES+2' denotes the old implementation of find_best before
5529
the greedy version. Will be removed when greedy_search is approved.
5538
choose_plan(JOIN *join, table_map join_tables)
5540
uint32_t search_depth= join->thd->variables.optimizer_search_depth;
5541
uint32_t prune_level= join->thd->variables.optimizer_prune_level;
5542
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
5544
join->cur_embedding_map= 0;
5545
reset_nj_counters(join->join_list);
5547
if (SELECT_STRAIGHT_JOIN option is set)
5548
reorder tables so dependent tables come after tables they depend
5549
on, otherwise keep tables in the order they were specified in the query
5551
Apply heuristic: pre-sort all access plans with respect to the number of
5554
my_qsort(join->best_ref + join->const_tables,
5555
join->tables - join->const_tables, sizeof(JOIN_TAB*),
5556
straight_join ? join_tab_cmp_straight : join_tab_cmp);
5557
join->cur_emb_sj_nests= 0;
5560
optimize_straight_join(join, join_tables);
5564
if (search_depth == MAX_TABLES+2)
5566
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
5567
the greedy version. Will be removed when greedy_search is approved.
5569
join->best_read= DBL_MAX;
5570
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
5575
if (search_depth == 0)
5576
/* Automatically determine a reasonable value for 'search_depth' */
5577
search_depth= determine_search_depth(join);
5578
if (greedy_search(join, join_tables, search_depth, prune_level))
5584
Store the cost of this query into a user variable
5585
Don't update last_query_cost for statements that are not "flat joins" :
5586
i.e. they have subqueries, unions or call stored procedures.
5587
TODO: calculate a correct cost for a query with subqueries and UNIONs.
5589
if (join->thd->lex->is_single_level_stmt())
5590
join->thd->status_var.last_query_cost= join->best_read;
5596
Compare two JOIN_TAB objects based on the number of accessed records.
5598
@param ptr1 pointer to first JOIN_TAB object
5599
@param ptr2 pointer to second JOIN_TAB object
793
5602
The order relation implemented by join_tab_cmp() is not transitive,
5656
Heuristic procedure to automatically guess a reasonable degree of
5657
exhaustiveness for the greedy search procedure.
5659
The procedure estimates the optimization time and selects a search depth
5660
big enough to result in a near-optimal QEP, that doesn't take too long to
5661
find. If the number of tables in the query exceeds some constant, then
5662
search_depth is set to this constant.
5664
@param join pointer to the structure providing all context info for
5668
This is an extremely simplistic implementation that serves as a stub for a
5669
more advanced analysis of the join. Ideally the search depth should be
5670
determined by learning from previous query optimizations, because it will
5671
depend on the CPU power (and other factors).
5674
this value should be determined dynamically, based on statistics:
5675
uint32_t max_tables_for_exhaustive_opt= 7;
5678
this value could be determined by some mapping of the form:
5679
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5682
A positive integer that specifies the search depth (and thus the
5683
exhaustiveness) of the depth-first search algorithm used by
5688
determine_search_depth(JOIN *join)
5690
uint32_t table_count= join->tables - join->const_tables;
5691
uint32_t search_depth;
5692
/* TODO: this value should be determined dynamically, based on statistics: */
5693
uint32_t max_tables_for_exhaustive_opt= 7;
5695
if (table_count <= max_tables_for_exhaustive_opt)
5696
search_depth= table_count+1; // use exhaustive for small number of tables
5699
TODO: this value could be determined by some mapping of the form:
5700
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5702
search_depth= max_tables_for_exhaustive_opt; // use greedy search
5704
return search_depth;
5709
Select the best ways to access the tables in a query without reordering them.
5711
Find the best access paths for each query table and compute their costs
5712
according to their order in the array 'join->best_ref' (thus without
5713
reordering the join tables). The function calls sequentially
5714
'best_access_path' for each table in the query to select the best table
5715
access method. The final optimal plan is stored in the array
5716
'join->best_positions', and the corresponding cost in 'join->best_read'.
5718
@param join pointer to the structure providing all context info for
5720
@param join_tables set of the tables in the query
5723
This function can be applied to:
5724
- queries with STRAIGHT_JOIN
5725
- internally to compute the cost of an arbitrary QEP
5727
Thus 'optimize_straight_join' can be used at any stage of the query
5728
optimization process to finalize a QEP as it is.
5732
optimize_straight_join(JOIN *join, table_map join_tables)
5735
uint32_t idx= join->const_tables;
5736
double record_count= 1.0;
5737
double read_time= 0.0;
5739
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
5741
/* Find the best access method from 's' to the current partial plan */
5742
advance_sj_state(join_tables, s);
5743
best_access_path(join, s, join->thd, join_tables, idx,
5744
record_count, read_time);
5745
/* compute the cost of the new plan extended with 's' */
5746
record_count*= join->positions[idx].records_read;
5747
read_time+= join->positions[idx].read_time;
5748
join_tables&= ~(s->table->map);
5752
read_time+= record_count / (double) TIME_FOR_COMPARE;
5753
if (join->sort_by_table &&
5754
join->sort_by_table != join->positions[join->const_tables].table->table)
5755
read_time+= record_count; // We have to make a temp table
5756
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
5757
join->best_read= read_time;
5762
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
5764
The search procedure uses a hybrid greedy/exhaustive search with controlled
5765
exhaustiveness. The search is performed in N = card(remaining_tables)
5766
steps. Each step evaluates how promising is each of the unoptimized tables,
5767
selects the most promising table, and extends the current partial QEP with
5768
that table. Currenly the most 'promising' table is the one with least
5769
expensive extension.\
5771
There are two extreme cases:
5772
-# When (card(remaining_tables) < search_depth), the estimate finds the
5773
best complete continuation of the partial QEP. This continuation can be
5774
used directly as a result of the search.
5775
-# When (search_depth == 1) the 'best_extension_by_limited_search'
5776
consideres the extension of the current QEP with each of the remaining
5779
All other cases are in-between these two extremes. Thus the parameter
5780
'search_depth' controlls the exhaustiveness of the search. The higher the
5781
value, the longer the optimizaton time and possibly the better the
5782
resulting plan. The lower the value, the fewer alternative plans are
5783
estimated, but the more likely to get a bad QEP.
5785
All intermediate and final results of the procedure are stored in 'join':
5786
- join->positions : modified for every partial QEP that is explored
5787
- join->best_positions: modified for the current best complete QEP
5788
- join->best_read : modified for the current best complete QEP
5789
- join->best_ref : might be partially reordered
5791
The final optimal plan is stored in 'join->best_positions', and its
5792
corresponding cost in 'join->best_read'.
5795
The following pseudocode describes the algorithm of 'greedy_search':
5798
procedure greedy_search
5799
input: remaining_tables
5804
(t, a) = best_extension(pplan, remaining_tables);
5805
pplan = concat(pplan, (t, a));
5806
remaining_tables = remaining_tables - t;
5807
} while (remaining_tables != {})
5812
where 'best_extension' is a placeholder for a procedure that selects the
5813
most "promising" of all tables in 'remaining_tables'.
5814
Currently this estimate is performed by calling
5815
'best_extension_by_limited_search' to evaluate all extensions of the
5816
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
5817
mainly depends on that of 'best_extension_by_limited_search'.
5820
If 'best_extension()' == 'best_extension_by_limited_search()', then the
5821
worst-case complexity of this algorithm is <=
5822
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
5823
complexity of greedy_search is O(N!).
5826
In the future, 'greedy_search' might be extended to support other
5827
implementations of 'best_extension', e.g. some simpler quadratic procedure.
5829
@param join pointer to the structure providing all context info
5831
@param remaining_tables set of tables not included into the partial plan yet
5832
@param search_depth controlls the exhaustiveness of the search
5833
@param prune_level the pruning heuristics that should be applied during
5843
greedy_search(JOIN *join,
5844
table_map remaining_tables,
5845
uint32_t search_depth,
5846
uint32_t prune_level)
5848
double record_count= 1.0;
5849
double read_time= 0.0;
5850
uint32_t idx= join->const_tables; // index into 'join->best_ref'
5852
uint32_t size_remain; // cardinality of remaining_tables
5854
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
5856
/* number of tables that remain to be optimized */
5857
size_remain= my_count_bits(remaining_tables);
5860
/* Find the extension of the current QEP with the lowest cost */
5861
join->best_read= DBL_MAX;
5862
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
5863
read_time, search_depth, prune_level))
5866
if (size_remain <= search_depth)
5869
'join->best_positions' contains a complete optimal extension of the
5870
current partial QEP.
5875
/* select the first table in the optimal extension as most promising */
5876
best_pos= join->best_positions[idx];
5877
best_table= best_pos.table;
5879
Each subsequent loop of 'best_extension_by_limited_search' uses
5880
'join->positions' for cost estimates, therefore we have to update its
5883
join->positions[idx]= best_pos;
5885
/* find the position of 'best_table' in 'join->best_ref' */
5887
JOIN_TAB *pos= join->best_ref[best_idx];
5888
while (pos && best_table != pos)
5889
pos= join->best_ref[++best_idx];
5890
assert((pos != NULL)); // should always find 'best_table'
5891
/* move 'best_table' at the first free position in the array of joins */
5892
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
5894
/* compute the cost of the new plan extended with 'best_table' */
5895
record_count*= join->positions[idx].records_read;
5896
read_time+= join->positions[idx].read_time;
5898
remaining_tables&= ~(best_table->table->map);
5906
Find a good, possibly optimal, query execution plan (QEP) by a possibly
5909
The procedure searches for the optimal ordering of the query tables in set
5910
'remaining_tables' of size N, and the corresponding optimal access paths to
5911
each table. The choice of a table order and an access path for each table
5912
constitutes a query execution plan (QEP) that fully specifies how to
5915
The maximal size of the found plan is controlled by the parameter
5916
'search_depth'. When search_depth == N, the resulting plan is complete and
5917
can be used directly as a QEP. If search_depth < N, the found plan consists
5918
of only some of the query tables. Such "partial" optimal plans are useful
5919
only as input to query optimization procedures, and cannot be used directly
5922
The algorithm begins with an empty partial plan stored in 'join->positions'
5923
and a set of N tables - 'remaining_tables'. Each step of the algorithm
5924
evaluates the cost of the partial plan extended by all access plans for
5925
each of the relations in 'remaining_tables', expands the current partial
5926
plan with the access plan that results in lowest cost of the expanded
5927
partial plan, and removes the corresponding relation from
5928
'remaining_tables'. The algorithm continues until it either constructs a
5929
complete optimal plan, or constructs an optimal plartial plan with size =
5932
The final optimal plan is stored in 'join->best_positions'. The
5933
corresponding cost of the optimal plan is in 'join->best_read'.
5936
The procedure uses a recursive depth-first search where the depth of the
5937
recursion (and thus the exhaustiveness of the search) is controlled by the
5938
parameter 'search_depth'.
5941
The pseudocode below describes the algorithm of
5942
'best_extension_by_limited_search'. The worst-case complexity of this
5943
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
5944
the complexity of greedy_search is O(N!).
5947
procedure best_extension_by_limited_search(
5948
pplan in, // in, partial plan of tables-joined-so-far
5949
pplan_cost, // in, cost of pplan
5950
remaining_tables, // in, set of tables not referenced in pplan
5951
best_plan_so_far, // in/out, best plan found so far
5952
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5953
search_depth) // in, maximum size of the plans being considered
5955
for each table T from remaining_tables
5957
// Calculate the cost of using table T as above
5958
cost = complex-series-of-calculations;
5960
// Add the cost to the cost so far.
5963
if (pplan_cost >= best_plan_so_far_cost)
5964
// pplan_cost already too great, stop search
5967
pplan= expand pplan by best_access_method;
5968
remaining_tables= remaining_tables - table T;
5969
if (remaining_tables is not an empty set
5973
best_extension_by_limited_search(pplan, pplan_cost,
5976
best_plan_so_far_cost,
5981
best_plan_so_far_cost= pplan_cost;
5982
best_plan_so_far= pplan;
5989
When 'best_extension_by_limited_search' is called for the first time,
5990
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
5991
The actual implementation provides a way to optionally use pruning
5992
heuristic (controlled by the parameter 'prune_level') to reduce the search
5993
space by skipping some partial plans.
5996
The parameter 'search_depth' provides control over the recursion
5997
depth, and thus the size of the resulting optimal plan.
5999
@param join pointer to the structure providing all context info
6001
@param remaining_tables set of tables not included into the partial plan yet
6002
@param idx length of the partial QEP in 'join->positions';
6003
since a depth-first search is used, also corresponds
6004
to the current depth of the search tree;
6005
also an index in the array 'join->best_ref';
6006
@param record_count estimate for the number of records returned by the
6008
@param read_time the cost of the best partial plan
6009
@param search_depth maximum depth of the recursion and thus size of the
6011
(0 < search_depth <= join->tables+1).
6012
@param prune_level pruning heuristics that should be applied during
6014
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
6023
best_extension_by_limited_search(JOIN *join,
6024
table_map remaining_tables,
6026
double record_count,
6028
uint32_t search_depth,
6029
uint32_t prune_level)
6031
THD *thd= join->thd;
6032
if (thd->killed) // Abort
6036
'join' is a partial plan with lower cost than the best plan so far,
6037
so continue expanding it further with the tables in 'remaining_tables'.
6040
double best_record_count= DBL_MAX;
6041
double best_read_time= DBL_MAX;
6043
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
6045
table_map real_table_bit= s->table->map;
6046
if ((remaining_tables & real_table_bit) &&
6047
!(remaining_tables & s->dependent) &&
6048
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6050
double current_record_count, current_read_time;
6051
advance_sj_state(remaining_tables, s);
6054
psergey-insideout-todo:
6055
when best_access_path() detects it could do an InsideOut scan or
6056
some other scan, have it return an insideout scan and a flag that
6057
requests to "fork" this loop iteration. (Q: how does that behave
6058
when the depth is insufficient??)
6060
/* Find the best access method from 's' to the current partial plan */
6061
best_access_path(join, s, thd, remaining_tables, idx,
6062
record_count, read_time);
6063
/* Compute the cost of extending the plan with 's' */
6064
current_record_count= record_count * join->positions[idx].records_read;
6065
current_read_time= read_time + join->positions[idx].read_time;
6067
/* Expand only partial plans with lower cost than the best QEP so far */
6068
if ((current_read_time +
6069
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
6071
restore_prev_nj_state(s);
6072
restore_prev_sj_state(remaining_tables, s);
6077
Prune some less promising partial plans. This heuristic may miss
6078
the optimal QEPs, thus it results in a non-exhaustive search.
6080
if (prune_level == 1)
6082
if (best_record_count > current_record_count ||
6083
best_read_time > current_read_time ||
6084
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
6086
if (best_record_count >= current_record_count &&
6087
best_read_time >= current_read_time &&
6088
/* TODO: What is the reasoning behind this condition? */
6089
(!(s->key_dependent & remaining_tables) ||
6090
join->positions[idx].records_read < 2.0))
6092
best_record_count= current_record_count;
6093
best_read_time= current_read_time;
6098
restore_prev_nj_state(s);
6099
restore_prev_sj_state(remaining_tables, s);
6104
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
6105
{ /* Recursively expand the current partial plan */
6106
std::swap(join->best_ref[idx], *pos);
6107
if (best_extension_by_limited_search(join,
6108
remaining_tables & ~real_table_bit,
6110
current_record_count,
6115
std::swap(join->best_ref[idx], *pos);
6119
'join' is either the best partial QEP with 'search_depth' relations,
6120
or the best complete QEP so far, whichever is smaller.
6122
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
6123
if (join->sort_by_table &&
6124
join->sort_by_table !=
6125
join->positions[join->const_tables].table->table)
6126
/* We have to make a temp table */
6127
current_read_time+= current_record_count;
6128
if ((search_depth == 1) || (current_read_time < join->best_read))
6130
memcpy(join->best_positions, join->positions,
6131
sizeof(POSITION) * (idx + 1));
6132
join->best_read= current_read_time - 0.001;
6135
restore_prev_nj_state(s);
6136
restore_prev_sj_state(remaining_tables, s);
6145
- TODO: this function is here only temporarily until 'greedy_search' is
6146
tested and accepted.
6153
find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count,
6156
THD *thd= join->thd;
6161
read_time+=record_count/(double) TIME_FOR_COMPARE;
6162
if (join->sort_by_table &&
6163
join->sort_by_table !=
6164
join->positions[join->const_tables].table->table)
6165
read_time+=record_count; // We have to make a temp table
6166
if (read_time < join->best_read)
6168
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
6169
join->best_read= read_time - 0.001;
6173
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
6174
return(false); /* Found better before */
6177
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
6178
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
6180
table_map real_table_bit=s->table->map;
6181
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
6182
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6184
double records, best;
6185
advance_sj_state(rest_tables, s);
6186
best_access_path(join, s, thd, rest_tables, idx, record_count,
6188
records= join->positions[idx].records_read;
6189
best= join->positions[idx].read_time;
6191
Go to the next level only if there hasn't been a better key on
6192
this level! This will cut down the search for a lot simple cases!
6194
double current_record_count=record_count*records;
6195
double current_read_time=read_time+best;
6196
if (best_record_count > current_record_count ||
6197
best_read_time > current_read_time ||
6198
(idx == join->const_tables && s->table == join->sort_by_table))
6200
if (best_record_count >= current_record_count &&
6201
best_read_time >= current_read_time &&
6202
(!(s->key_dependent & rest_tables) || records < 2.0))
6204
best_record_count=current_record_count;
6205
best_read_time=current_read_time;
6207
std::swap(join->best_ref[idx], *pos);
6208
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
6209
current_record_count,current_read_time))
6211
std::swap(join->best_ref[idx], *pos);
6213
restore_prev_nj_state(s);
6214
restore_prev_sj_state(rest_tables, s);
6215
if (join->select_options & SELECT_STRAIGHT_JOIN)
6216
break; // Don't test all combinations
842
6224
Find how much space the prevous read not const tables takes in cache.
844
void calc_used_field_length(Session *, JoinTable *join_tab)
6227
static void calc_used_field_length(THD *thd __attribute__((unused)),
846
6230
uint32_t null_fields,blobs,fields,rec_length;
847
6231
Field **f_ptr,*field;
6232
MY_BITMAP *read_set= join_tab->table->read_set;;
849
6234
null_fields= blobs= fields= rec_length=0;
850
for (f_ptr=join_tab->table->getFields() ; (field= *f_ptr) ; f_ptr++)
6235
for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++)
852
if (field->isReadSet())
6237
if (bitmap_is_set(read_set, field->field_index))
854
6239
uint32_t flags=field->flags;
856
6241
rec_length+=field->pack_length();
857
6242
if (flags & BLOB_FLAG)
859
6244
if (!(flags & NOT_NULL_FLAG))
863
6248
if (null_fields)
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
THD *thd= join->thd;
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
thd->lex->current_select->master_unit() ==
6936
&thd->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
(uint) 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
thd->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 (thd->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.is_clear_all() && tab->type != JT_EQ_REF
7086
&& (tab->type != JT_REF || (uint) tab->ref.key == tab->quick->index))
7088
sel->quick=tab->quick; // Use value from get_quick_...
7089
sel->quick_keys.clear_all();
7090
sel->needed_reg.clear_all();
7098
uint32_t ref_key=(uint) sel->head->reginfo.join_tab->ref.key+1;
7099
if (i == join->const_tables && ref_key)
7101
if (!tab->const_keys.is_clear_all() &&
7102
tab->table->reginfo.impossible_range)
7105
else if (tab->type == JT_ALL && ! use_quick_range)
7107
if (!tab->const_keys.is_clear_all() &&
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.is_subset(tab->const_keys) && i > 0)) ||
7118
(!tab->const_keys.is_clear_all() && (i == join->const_tables) && (join->unit->select_limit_cnt < join->best_positions[i].records_read) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
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(thd, 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(thd, 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.clear_all();
7169
if (!sel->quick_keys.is_subset(tab->checked_keys) ||
7170
!sel->needed_reg.is_subset(tab->checked_keys))
7172
tab->keys=sel->quick_keys;
7173
tab->keys.merge(sel->needed_reg);
7174
tab->use_quick= (!sel->needed_reg.is_clear_all() &&
7175
(select->quick_keys.is_clear_all() ||
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
thd->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
COND *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
Check if given expression uses only table fields covered by the given index
7290
uses_index_fields_only()
7291
item Expression to check
7292
tbl The table having the index
7293
keyno The index number
7294
other_tbls_ok true <=> Fields of other non-const tables are allowed
7297
Check if given expression only uses fields covered by index #keyno in the
7298
table tbl. The expression can use any fields in any other tables.
7300
The expression is guaranteed not to be AND or OR - those constructs are
7301
handled outside of this function.
7308
bool uses_index_fields_only(Item *item, Table *tbl, uint32_t keyno,
7311
if (item->const_item())
7315
Don't push down the triggered conditions. Nested outer joins execution
7316
code may need to evaluate a condition several times (both triggered and
7317
untriggered), and there is no way to put thi
7318
TODO: Consider cloning the triggered condition and using the copies for:
7319
1. push the first copy down, to have most restrictive index condition
7321
2. Put the second copy into tab->select_cond.
7323
if (item->type() == Item::FUNC_ITEM &&
7324
((Item_func*)item)->functype() == Item_func::TRIG_COND_FUNC)
7327
if (!(item->used_tables() & tbl->map))
7328
return other_tbls_ok;
7330
Item::Type item_type= item->type();
7331
switch (item_type) {
7332
case Item::FUNC_ITEM:
7334
/* This is a function, apply condition recursively to arguments */
7335
Item_func *item_func= (Item_func*)item;
7337
Item **item_end= (item_func->arguments()) + item_func->argument_count();
7338
for (child= item_func->arguments(); child != item_end; child++)
7340
if (!uses_index_fields_only(*child, tbl, keyno, other_tbls_ok))
7345
case Item::COND_ITEM:
7347
/* This is a function, apply condition recursively to arguments */
7348
List_iterator<Item> li(*((Item_cond*)item)->argument_list());
7352
if (!uses_index_fields_only(item, tbl, keyno, other_tbls_ok))
7357
case Item::FIELD_ITEM:
7359
Item_field *item_field= (Item_field*)item;
7360
if (item_field->field->table != tbl)
7362
return item_field->field->part_of_key.is_set(keyno);
7364
case Item::REF_ITEM:
7365
return uses_index_fields_only(item->real_item(), tbl, keyno,
7368
return false; /* Play it safe, don't push unknown non-const items */
1209
7373
#define ICP_COND_USES_INDEX_ONLY 10
1215
void JoinTable::cleanup()
7376
Get a part of the condition that can be checked using only index fields
7379
make_cond_for_index()
7380
cond The source condition
7381
table The table that is partially available
7382
keyno The index in the above table. Only fields covered by the index
7384
other_tbls_ok true <=> Fields of other non-const tables are allowed
7387
Get a part of the condition that can be checked when for the given table
7388
we have values only of fields covered by some index. The condition may
7389
refer to other tables, it is assumed that we have values of all of their
7393
make_cond_for_index(
7394
"cond(t1.field) AND cond(t2.key1) AND cond(t2.non_key) AND cond(t2.key2)",
7397
"cond(t1.field) AND cond(t2.key2)"
7400
Index condition, or NULL if no condition could be inferred.
7403
Item *make_cond_for_index(Item *cond, Table *table, uint32_t keyno,
7408
if (cond->type() == Item::COND_ITEM)
7410
uint32_t n_marked= 0;
7411
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7413
Item_cond_and *new_cond=new Item_cond_and;
7416
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7420
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7422
new_cond->argument_list()->push_back(fix);
7423
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7425
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7426
cond->marker= ICP_COND_USES_INDEX_ONLY;
7427
switch (new_cond->argument_list()->elements) {
7431
return new_cond->argument_list()->head();
7433
new_cond->quick_fix_field();
7439
Item_cond_or *new_cond=new Item_cond_or;
7442
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7446
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7449
new_cond->argument_list()->push_back(fix);
7450
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7452
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7453
cond->marker= ICP_COND_USES_INDEX_ONLY;
7454
new_cond->quick_fix_field();
7455
new_cond->top_level_item();
7460
if (!uses_index_fields_only(cond, table, keyno, other_tbls_ok))
7462
cond->marker= ICP_COND_USES_INDEX_ONLY;
7467
Item *make_cond_remainder(Item *cond, bool exclude_index)
7469
if (exclude_index && cond->marker == ICP_COND_USES_INDEX_ONLY)
7470
return 0; /* Already checked */
7472
if (cond->type() == Item::COND_ITEM)
7474
table_map tbl_map= 0;
7475
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7477
/* Create new top level AND item */
7478
Item_cond_and *new_cond=new Item_cond_and;
7481
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7485
Item *fix= make_cond_remainder(item, exclude_index);
7488
new_cond->argument_list()->push_back(fix);
7489
tbl_map |= fix->used_tables();
7492
switch (new_cond->argument_list()->elements) {
7496
return new_cond->argument_list()->head();
7498
new_cond->quick_fix_field();
7499
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7505
Item_cond_or *new_cond=new Item_cond_or;
7508
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7512
Item *fix= make_cond_remainder(item, false);
7515
new_cond->argument_list()->push_back(fix);
7516
tbl_map |= fix->used_tables();
7518
new_cond->quick_fix_field();
7519
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7520
new_cond->top_level_item();
7529
Try to extract and push the index condition
7533
tab A join tab that has tab->table->file and its condition
7535
keyno Index for which extract and push the condition
7536
other_tbls_ok true <=> Fields of other non-const tables are allowed
7539
Try to extract and push the index condition down to table handler
7542
static void push_index_cond(JOIN_TAB *tab, uint32_t keyno, bool other_tbls_ok)
7545
if (tab->table->file->index_flags(keyno, 0, 1) & HA_DO_INDEX_COND_PUSHDOWN &&
7546
tab->join->thd->variables.engine_condition_pushdown)
7548
idx_cond= make_cond_for_index(tab->select_cond, tab->table, keyno,
7553
tab->pre_idx_push_select_cond= tab->select_cond;
7554
Item *idx_remainder_cond=
7555
tab->table->file->idx_cond_push(keyno, idx_cond);
7558
Disable eq_ref's "lookup cache" if we've pushed down an index
7560
TODO: This check happens to work on current ICP implementations, but
7561
there may exist a compliant implementation that will not work
7562
correctly with it. Sort this out when we stabilize the condition
7565
if (idx_remainder_cond != idx_cond)
7566
tab->ref.disable_cache= true;
7568
Item *row_cond= make_cond_remainder(tab->select_cond, true);
7572
if (!idx_remainder_cond)
7573
tab->select_cond= row_cond;
7576
tab->select_cond= new Item_cond_and(row_cond, idx_remainder_cond);
7577
tab->select_cond->quick_fix_field();
7578
((Item_cond_and*)tab->select_cond)->used_tables_cache=
7579
row_cond->used_tables() | idx_remainder_cond->used_tables();
7583
tab->select_cond= idx_remainder_cond;
7586
tab->select->cond= tab->select_cond;
7596
Determine if the set is already ordered for order_st BY, so it can
7597
disable join cache because it will change the ordering of the results.
7598
Code handles sort table that is at any location (not only first after
7599
the const tables) despite the fact that it's currently prohibited.
7600
We must disable join cache if the first non-const table alone is
7601
ordered. If there is a temp table the ordering is done as a last
7602
operation and doesn't prevent join cache usage.
7604
uint32_t make_join_orderinfo(JOIN *join)
7608
return join->tables;
7610
for (i=join->const_tables ; i < join->tables ; i++)
7612
JOIN_TAB *tab=join->join_tab+i;
7613
Table *table=tab->table;
7614
if ((table == join->sort_by_table &&
7615
(!join->order || join->skip_sort_order)) ||
7616
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
7626
Plan refinement stage: do various set ups for the executioner
7629
make_join_readinfo()
7630
join Join being processed
7631
options Join's options (checking for SELECT_DESCRIBE,
7632
SELECT_NO_JOIN_CACHE)
7633
no_jbuf_after Don't use join buffering after table with this number.
7636
Plan refinement stage: do various set ups for the executioner
7637
- set up use of join buffering
7638
- push index conditions
7639
- increment counters
7644
true - Out of memory
7648
make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
7651
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
7654
for (i=join->const_tables ; i < join->tables ; i++)
7656
JOIN_TAB *tab=join->join_tab+i;
7657
Table *table=tab->table;
7658
bool using_join_cache;
7659
tab->read_record.table= table;
7660
tab->read_record.file=table->file;
7661
tab->next_select=sub_select; /* normal select */
7663
TODO: don't always instruct first table's ref/range access method to
7664
produce sorted output.
7666
tab->sorted= sorted;
7667
sorted= 0; // only first must be sorted
7668
if (tab->insideout_match_tab)
7670
if (!(tab->insideout_buf= (unsigned char*)join->thd->alloc(tab->table->key_info
7675
switch (tab->type) {
7676
case JT_SYSTEM: // Only happens with left join
7677
table->status=STATUS_NO_RECORD;
7678
tab->read_first_record= join_read_system;
7679
tab->read_record.read_record= join_no_more_records;
7681
case JT_CONST: // Only happens with left join
7682
table->status=STATUS_NO_RECORD;
7683
tab->read_first_record= join_read_const;
7684
tab->read_record.read_record= join_no_more_records;
7685
if (table->covering_keys.is_set(tab->ref.key) &&
7689
table->file->extra(HA_EXTRA_KEYREAD);
7693
table->status=STATUS_NO_RECORD;
7696
delete tab->select->quick;
7697
tab->select->quick=0;
7701
tab->read_first_record= join_read_key;
7702
tab->read_record.read_record= join_no_more_records;
7703
if (table->covering_keys.is_set(tab->ref.key) &&
7707
table->file->extra(HA_EXTRA_KEYREAD);
7710
push_index_cond(tab, tab->ref.key, true);
7712
case JT_REF_OR_NULL:
7714
table->status=STATUS_NO_RECORD;
7717
delete tab->select->quick;
7718
tab->select->quick=0;
7722
if (table->covering_keys.is_set(tab->ref.key) &&
7726
table->file->extra(HA_EXTRA_KEYREAD);
7729
push_index_cond(tab, tab->ref.key, true);
7730
if (tab->type == JT_REF)
7732
tab->read_first_record= join_read_always_key;
7733
tab->read_record.read_record= tab->insideout_match_tab?
7734
join_read_next_same_diff : join_read_next_same;
7738
tab->read_first_record= join_read_always_key_or_null;
7739
tab->read_record.read_record= join_read_next_same_or_null;
7744
If previous table use cache
7745
If the incoming data set is already sorted don't use cache.
7747
table->status=STATUS_NO_RECORD;
7748
using_join_cache= false;
7749
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
7750
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
7751
!tab->insideout_match_tab)
7753
if ((options & SELECT_DESCRIBE) ||
7754
!join_init_cache(join->thd,join->join_tab+join->const_tables,
7755
i-join->const_tables))
7757
using_join_cache= true;
7758
tab[-1].next_select=sub_select_cache; /* Patch previous */
7761
/* These init changes read_record */
7762
if (tab->use_quick == 2)
7764
join->thd->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
7765
tab->read_first_record= join_init_quick_read_record;
7767
status_var_increment(join->thd->status_var.select_range_check_count);
7771
tab->read_first_record= join_init_read_record;
7772
if (i == join->const_tables)
7774
if (tab->select && tab->select->quick)
7777
status_var_increment(join->thd->status_var.select_range_count);
7781
join->thd->server_status|=SERVER_QUERY_NO_INDEX_USED;
7783
status_var_increment(join->thd->status_var.select_scan_count);
7788
if (tab->select && tab->select->quick)
7791
status_var_increment(join->thd->status_var.select_full_range_join_count);
7795
join->thd->server_status|=SERVER_QUERY_NO_INDEX_USED;
7797
status_var_increment(join->thd->status_var.select_full_join_count);
7800
if (!table->no_keyread)
7802
if (tab->select && tab->select->quick &&
7803
tab->select->quick->index != MAX_KEY && //not index_merge
7804
table->covering_keys.is_set(tab->select->quick->index))
7807
table->file->extra(HA_EXTRA_KEYREAD);
7809
else if (!table->covering_keys.is_clear_all() &&
7810
!(tab->select && tab->select->quick))
7811
{ // Only read index tree
7812
if (!tab->insideout_match_tab)
7815
See bug #26447: "Using the clustered index for a table scan
7816
is always faster than using a secondary index".
7818
if (table->s->primary_key != MAX_KEY &&
7819
table->file->primary_key_is_clustered())
7820
tab->index= table->s->primary_key;
7822
tab->index= table->find_shortest_key(&table->covering_keys);
7824
tab->read_first_record= join_read_first;
7825
tab->type=JT_NEXT; // Read with index_first / index_next
7828
if (tab->select && tab->select->quick &&
7829
tab->select->quick->index != MAX_KEY && ! tab->table->key_read)
7830
push_index_cond(tab, tab->select->quick->index, !using_join_cache);
7834
break; /* purecov: deadcode */
7837
abort(); /* purecov: deadcode */
7840
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
7846
Give error if we some tables are done with a full join.
7848
This is used by multi_table_update and multi_table_delete when running
7851
@param join Join condition
7856
1 Error (full join used)
7859
bool error_if_full_join(JOIN *join)
7861
for (JOIN_TAB *tab=join->join_tab, *end=join->join_tab+join->tables;
7865
if (tab->type == JT_ALL && (!tab->select || !tab->select->quick))
7867
my_message(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE,
7868
ER(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE), MYF(0));
7880
void JOIN_TAB::cleanup()
1221
7886
if (cache.buff)
1223
size_t size= cache.end - cache.buff;
1224
global_join_buffer.sub(size);
1225
7887
free(cache.buff);
2508
9606
if (!(left_const && right_const) &&
2509
9607
args[0]->result_type() == args[1]->result_type())
2513
resolve_const_item(session, &args[1], args[0]);
2514
func->update_used_tables();
2515
change_cond_ref_to_const(session, save_list, and_father, and_father,
2518
else if (left_const)
2520
resolve_const_item(session, &args[0], args[1]);
2521
func->update_used_tables();
2522
change_cond_ref_to_const(session, save_list, and_father, and_father,
9611
resolve_const_item(thd, &args[1], args[0]);
9612
func->update_used_tables();
9613
change_cond_ref_to_const(thd, save_list, and_father, and_father,
9616
else if (left_const)
9618
resolve_const_item(thd, &args[0], args[1]);
9619
func->update_used_tables();
9620
change_cond_ref_to_const(thd, save_list, and_father, and_father,
9630
Simplify joins replacing outer joins by inner joins whenever it's
9633
The function, during a retrieval of join_list, eliminates those
9634
outer joins that can be converted into inner join, possibly nested.
9635
It also moves the on expressions for the converted outer joins
9636
and from inner joins to conds.
9637
The function also calculates some attributes for nested joins:
9641
- on_expr_dep_tables
9642
The first two attributes are used to test whether an outer join can
9643
be substituted for an inner join. The third attribute represents the
9644
relation 'to be dependent on' for tables. If table t2 is dependent
9645
on table t1, then in any evaluated execution plan table access to
9646
table t2 must precede access to table t2. This relation is used also
9647
to check whether the query contains invalid cross-references.
9648
The forth attribute is an auxiliary one and is used to calculate
9650
As the attribute dep_tables qualifies possibles orders of tables in the
9651
execution plan, the dependencies required by the straight join
9652
modifiers are reflected in this attribute as well.
9653
The function also removes all braces that can be removed from the join
9654
expression without changing its meaning.
9657
An outer join can be replaced by an inner join if the where condition
9658
or the on expression for an embedding nested join contains a conjunctive
9659
predicate rejecting null values for some attribute of the inner tables.
9663
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9665
the predicate t2.b < 5 rejects nulls.
9666
The query is converted first to:
9668
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9670
then to the equivalent form:
9672
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
9676
Similarly the following query:
9678
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
9683
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
9687
One conversion might trigger another:
9689
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
9690
LEFT JOIN t3 ON t3.b=t2.b
9691
WHERE t3 IS NOT NULL =>
9692
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
9693
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
9694
SELECT * FROM t1, t2, t3
9695
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
9698
The function removes all unnecessary braces from the expression
9699
produced by the conversions.
9702
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9704
finally is converted to:
9706
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9711
It also will remove braces from the following queries:
9713
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
9714
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
9717
The benefit of this simplification procedure is that it might return
9718
a query for which the optimizer can evaluate execution plan with more
9719
join orders. With a left join operation the optimizer does not
9720
consider any plan where one of the inner tables is before some of outer
9724
The function is implemented by a recursive procedure. On the recursive
9725
ascent all attributes are calculated, all outer joins that can be
9726
converted are replaced and then all unnecessary braces are removed.
9727
As join list contains join tables in the reverse order sequential
9728
elimination of outer joins does not require extra recursive calls.
9731
Remove all semi-joins that have are within another semi-join (i.e. have
9732
an "ancestor" semi-join nest)
9735
Here is an example of a join query with invalid cross references:
9737
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
9740
@param join reference to the query info
9741
@param join_list list representation of the join to be converted
9742
@param conds conditions to add on expressions for converted joins
9743
@param top true <=> conds is the where condition
9746
- The new condition, if success
9751
simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top,
9755
nested_join_st *nested_join;
9756
TableList *prev_table= 0;
9757
List_iterator<TableList> li(*join_list);
9760
Try to simplify join operations from join_list.
9761
The most outer join operation is checked for conversion first.
9763
while ((table= li++))
9765
table_map used_tables;
9766
table_map not_null_tables= (table_map) 0;
9768
if ((nested_join= table->nested_join))
9771
If the element of join_list is a nested join apply
9772
the procedure to its nested join list first.
9776
Item *expr= table->on_expr;
9778
If an on expression E is attached to the table,
9779
check all null rejected predicates in this expression.
9780
If such a predicate over an attribute belonging to
9781
an inner table of an embedded outer join is found,
9782
the outer join is converted to an inner join and
9783
the corresponding on expression is added to E.
9785
expr= simplify_joins(join, &nested_join->join_list,
9786
expr, false, in_sj || table->sj_on_expr);
9788
if (!table->prep_on_expr || expr != table->on_expr)
9792
table->on_expr= expr;
9793
table->prep_on_expr= expr->copy_andor_structure(join->thd);
9796
nested_join->used_tables= (table_map) 0;
9797
nested_join->not_null_tables=(table_map) 0;
9798
conds= simplify_joins(join, &nested_join->join_list, conds, top,
9799
in_sj || table->sj_on_expr);
9800
used_tables= nested_join->used_tables;
9801
not_null_tables= nested_join->not_null_tables;
9805
if (!table->prep_on_expr)
9806
table->prep_on_expr= table->on_expr;
9807
used_tables= table->table->map;
9809
not_null_tables= conds->not_null_tables();
9812
if (table->embedding)
9814
table->embedding->nested_join->used_tables|= used_tables;
9815
table->embedding->nested_join->not_null_tables|= not_null_tables;
9818
if (!table->outer_join || (used_tables & not_null_tables))
9821
For some of the inner tables there are conjunctive predicates
9822
that reject nulls => the outer join can be replaced by an inner join.
9824
table->outer_join= 0;
9827
/* Add ON expression to the WHERE or upper-level ON condition. */
9830
conds= and_conds(conds, table->on_expr);
9831
conds->top_level_item();
9832
/* conds is always a new item as both cond and on_expr existed */
9833
assert(!conds->fixed);
9834
conds->fix_fields(join->thd, &conds);
9837
conds= table->on_expr;
9838
table->prep_on_expr= table->on_expr= 0;
9846
Only inner tables of non-convertible outer joins
9847
remain with on_expr.
9851
table->dep_tables|= table->on_expr->used_tables();
9852
if (table->embedding)
9854
table->dep_tables&= ~table->embedding->nested_join->used_tables;
9856
Embedding table depends on tables used
9857
in embedded on expressions.
9859
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
9862
table->dep_tables&= ~table->table->map;
9867
/* The order of tables is reverse: prev_table follows table */
9868
if (prev_table->straight)
9869
prev_table->dep_tables|= used_tables;
9870
if (prev_table->on_expr)
9872
prev_table->dep_tables|= table->on_expr_dep_tables;
9873
table_map prev_used_tables= prev_table->nested_join ?
9874
prev_table->nested_join->used_tables :
9875
prev_table->table->map;
9877
If on expression contains only references to inner tables
9878
we still make the inner tables dependent on the outer tables.
9879
It would be enough to set dependency only on one outer table
9880
for them. Yet this is really a rare case.
9882
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
9883
prev_table->dep_tables|= used_tables;
9890
Flatten nested joins that can be flattened.
9891
no ON expression and not a semi-join => can be flattened.
9894
while ((table= li++))
9896
nested_join= table->nested_join;
9897
if (table->sj_on_expr && !in_sj)
9900
If this is a semi-join that is not contained within another semi-join,
9901
leave it intact (otherwise it is flattened)
9903
join->select_lex->sj_nests.push_back(table);
9905
else if (nested_join && !table->on_expr)
9908
List_iterator<TableList> it(nested_join->join_list);
9911
tbl->embedding= table->embedding;
9912
tbl->join_list= table->join_list;
9914
li.replace(nested_join->join_list);
9922
Assign each nested join structure a bit in nested_join_map.
9924
Assign each nested join structure (except "confluent" ones - those that
9925
embed only one element) a bit in nested_join_map.
9927
@param join Join being processed
9928
@param join_list List of tables
9929
@param first_unused Number of first unused bit in nested_join_map before the
9933
This function is called after simplify_joins(), when there are no
9934
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
9935
we will not run out of bits in nested_join_map.
9938
First unused bit in nested_join_map after the call.
9941
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
9942
uint32_t first_unused)
9944
List_iterator<TableList> li(*join_list);
9946
while ((table= li++))
9948
nested_join_st *nested_join;
9949
if ((nested_join= table->nested_join))
9952
It is guaranteed by simplify_joins() function that a nested join
9953
that has only one child is either
9954
- a single-table view (the child is the underlying table), or
9955
- a single-table semi-join nest
9957
We don't assign bits to such sj-nests because
9958
1. it is redundant (a "sequence" of one table cannot be interleaved
9960
2. we could run out bits in nested_join_map otherwise.
9962
if (nested_join->join_list.elements != 1)
9964
/* Don't assign bits to sj-nests */
9966
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
9967
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
9972
return(first_unused);
9977
Set nested_join_st::counter=0 in all nested joins in passed list.
9979
Recursively set nested_join_st::counter=0 for all nested joins contained in
9980
the passed join_list.
9982
@param join_list List of nested joins to process. It may also contain base
9983
tables which will be ignored.
9986
static void reset_nj_counters(List<TableList> *join_list)
9988
List_iterator<TableList> li(*join_list);
9990
while ((table= li++))
9992
nested_join_st *nested_join;
9993
if ((nested_join= table->nested_join))
9995
nested_join->counter_= 0;
9996
reset_nj_counters(&nested_join->join_list);
2531
10004
Check interleaving with an inner tables of an outer join for
2532
10005
extension table.
2534
Check if table next_tab can be added to current partial join order, and
10007
Check if table next_tab can be added to current partial join order, and
2535
10008
if yes, record that it has been added.
2537
10010
The function assumes that both current partial join order and its
2538
10011
extension with next_tab are valid wrt table dependencies.
2542
10015
LIMITATIONS ON JOIN order_st
2543
10016
The nested [outer] joins executioner algorithm imposes these limitations
2544
10017
on join order:
2545
1. "Outer tables first" - any "outer" table must be before any
10018
1. "Outer tables first" - any "outer" table must be before any
2546
10019
corresponding "inner" table.
2547
10020
2. "No interleaving" - tables inside a nested join must form a continuous
2548
sequence in join order (i.e. the sequence must not be interrupted by
10021
sequence in join order (i.e. the sequence must not be interrupted by
2549
10022
tables that are outside of this nested join).
2551
10024
#1 is checked elsewhere, this function checks #2 provided that #1 has
2552
10025
been already checked.
2554
10027
WHY NEED NON-INTERLEAVING
2555
Consider an example:
10028
Consider an example:
2557
10030
select * from t0 join t1 left join (t2 join t3) on cond1
3347
int safe_index_read(JoinTable *tab)
10910
SemiJoinDuplicateElimination: Weed out duplicate row combinations
10913
do_sj_dups_weedout()
10917
1 The row combination is a duplicate (discard it)
10918
0 The row combination is not a duplicate (continue)
10921
int do_sj_dups_weedout(THD *thd, SJ_TMP_TABLE *sjtbl)
10924
SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
10925
SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
10926
unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;
10927
unsigned char *nulls_ptr= ptr;
10929
/* Put the the rowids tuple into table->record[0]: */
10931
// 1. Store the length
10932
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
10934
*ptr= (unsigned char)(sjtbl->rowid_len + sjtbl->null_bytes);
10939
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
10943
// 2. Zero the null bytes
10944
if (sjtbl->null_bytes)
10946
memset(ptr, 0, sjtbl->null_bytes);
10947
ptr += sjtbl->null_bytes;
10950
// 3. Put the rowids
10951
for (uint32_t i=0; tab != tab_end; tab++, i++)
10953
handler *h= tab->join_tab->table->file;
10954
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
10956
/* It's a NULL-complemented row */
10957
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
10958
memset(ptr + tab->rowid_offset, 0, h->ref_length);
10962
/* Copy the rowid value */
10963
if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
10964
h->position(tab->join_tab->table->record[0]);
10965
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
10969
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
10972
/* create_myisam_from_heap will generate error if needed */
10973
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
10974
create_myisam_from_heap(thd, sjtbl->tmp_table, sjtbl->start_recinfo,
10975
&sjtbl->recinfo, error, 1))
10977
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
10985
SemiJoinDuplicateElimination: Reset the temporary table
10988
int do_sj_reset(SJ_TMP_TABLE *sj_tbl)
10990
if (sj_tbl->tmp_table)
10991
return sj_tbl->tmp_table->file->ha_delete_all_rows();
10996
Process one record of the nested loop join.
10998
This function will evaluate parts of WHERE/ON clauses that are
10999
applicable to the partial record on hand and in case of success
11000
submit this record to the next level of the nested loop.
11003
static enum_nested_loop_state
11004
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
11007
bool not_used_in_distinct=join_tab->not_used_in_distinct;
11008
ha_rows found_records=join->found_records;
11009
COND *select_cond= join_tab->select_cond;
11011
if (error > 0 || (join->thd->is_error())) // Fatal error
11012
return NESTED_LOOP_ERROR;
11014
return NESTED_LOOP_NO_MORE_ROWS;
11015
if (join->thd->killed) // Aborted by user
11017
join->thd->send_kill_message();
11018
return NESTED_LOOP_KILLED; /* purecov: inspected */
11020
if (!select_cond || select_cond->val_int())
11023
There is no select condition or the attached pushed down
11024
condition is true => a match is found.
11027
while (join_tab->first_unmatched && found)
11030
The while condition is always false if join_tab is not
11031
the last inner join table of an outer join operation.
11033
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11035
Mark that a match for current outer table is found.
11036
This activates push down conditional predicates attached
11037
to the all inner tables of the outer join.
11039
first_unmatched->found= 1;
11040
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11042
if (tab->table->reginfo.not_exists_optimize)
11043
return NESTED_LOOP_NO_MORE_ROWS;
11044
/* Check all predicates that has just been activated. */
11046
Actually all predicates non-guarded by first_unmatched->found
11047
will be re-evaluated again. It could be fixed, but, probably,
11048
it's not worth doing now.
11050
if (tab->select_cond && !tab->select_cond->val_int())
11052
/* The condition attached to table tab is false */
11053
if (tab == join_tab)
11058
Set a return point if rejected predicate is attached
11059
not to the last table of the current nest level.
11061
join->return_tab= tab;
11062
return NESTED_LOOP_OK;
11067
Check whether join_tab is not the last inner table
11068
for another embedding outer join.
11070
if ((first_unmatched= first_unmatched->first_upper) &&
11071
first_unmatched->last_inner != join_tab)
11072
first_unmatched= 0;
11073
join_tab->first_unmatched= first_unmatched;
11076
JOIN_TAB *return_tab= join->return_tab;
11077
join_tab->found_match= true;
11078
if (join_tab->check_weed_out_table)
11080
int res= do_sj_dups_weedout(join->thd, join_tab->check_weed_out_table);
11082
return NESTED_LOOP_ERROR;
11084
return NESTED_LOOP_OK;
11086
else if (join_tab->do_firstmatch)
11089
We should return to the join_tab->do_firstmatch after we have
11090
enumerated all the suffixes for current prefix row combination
11092
return_tab= join_tab->do_firstmatch;
11096
It was not just a return to lower loop level when one
11097
of the newly activated predicates is evaluated as false
11098
(See above join->return_tab= tab).
11100
join->examined_rows++;
11101
join->thd->row_count++;
11105
enum enum_nested_loop_state rc;
11106
/* A match from join_tab is found for the current partial join. */
11107
rc= (*join_tab->next_select)(join, join_tab+1, 0);
11108
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11110
if (return_tab < join->return_tab)
11111
join->return_tab= return_tab;
11113
if (join->return_tab < join_tab)
11114
return NESTED_LOOP_OK;
11116
Test if this was a SELECT DISTINCT query on a table that
11117
was not in the field list; In this case we can abort if
11118
we found a row, as no new rows can be added to the result.
11120
if (not_used_in_distinct && found_records != join->found_records)
11121
return NESTED_LOOP_NO_MORE_ROWS;
11124
join_tab->read_record.file->unlock_row();
11129
The condition pushed down to the table join_tab rejects all rows
11130
with the beginning coinciding with the current partial join.
11132
join->examined_rows++;
11133
join->thd->row_count++;
11134
join_tab->read_record.file->unlock_row();
11136
return NESTED_LOOP_OK;
11143
Construct a NULL complimented partial join record and feed it to the next
11144
level of the nested loop. This function is used in case we have
11145
an OUTER join and no matching record was found.
11148
static enum_nested_loop_state
11149
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab)
11152
The table join_tab is the first inner table of a outer join operation
11153
and no matches has been found for the current outer row.
11155
JOIN_TAB *last_inner_tab= join_tab->last_inner;
11156
/* Cache variables for faster loop */
11158
for ( ; join_tab <= last_inner_tab ; join_tab++)
11160
/* Change the the values of guard predicate variables. */
11161
join_tab->found= 1;
11162
join_tab->not_null_compl= 0;
11163
/* The outer row is complemented by nulls for each inner tables */
11164
restore_record(join_tab->table,s->default_values); // Make empty record
11165
mark_as_null_row(join_tab->table); // For group by without error
11166
select_cond= join_tab->select_cond;
11167
/* Check all attached conditions for inner table rows. */
11168
if (select_cond && !select_cond->val_int())
11169
return NESTED_LOOP_OK;
11173
The row complemented by nulls might be the first row
11174
of embedding outer joins.
11175
If so, perform the same actions as in the code
11176
for the first regular outer join row above.
11180
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11181
if ((first_unmatched= first_unmatched->first_upper) &&
11182
first_unmatched->last_inner != join_tab)
11183
first_unmatched= 0;
11184
join_tab->first_unmatched= first_unmatched;
11185
if (!first_unmatched)
11187
first_unmatched->found= 1;
11188
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11190
if (tab->select_cond && !tab->select_cond->val_int())
11192
join->return_tab= tab;
11193
return NESTED_LOOP_OK;
11198
The row complemented by nulls satisfies all conditions
11199
attached to inner tables.
11200
Send the row complemented by nulls to be joined with the
11203
return (*join_tab->next_select)(join, join_tab+1, 0);
11207
static enum_nested_loop_state
11208
flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skip_last)
11210
enum_nested_loop_state rc= NESTED_LOOP_OK;
11214
join_tab->table->null_row= 0;
11215
if (!join_tab->cache.records)
11216
return NESTED_LOOP_OK; /* Nothing to do */
11218
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
11219
if (join_tab->use_quick == 2)
11221
if (join_tab->select->quick)
11222
{ /* Used quick select last. reset it */
11223
delete join_tab->select->quick;
11224
join_tab->select->quick=0;
11227
/* read through all records */
11228
if ((error=join_init_read_record(join_tab)))
11230
reset_cache_write(&join_tab->cache);
11231
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
11234
for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
11236
tmp->status=tmp->table->status;
11237
tmp->table->status=0;
11240
info= &join_tab->read_record;
11243
if (join->thd->killed)
11245
join->thd->send_kill_message();
11246
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
11248
SQL_SELECT *select=join_tab->select;
11249
if (rc == NESTED_LOOP_OK &&
11250
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
11253
reset_cache_read(&join_tab->cache);
11254
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
11256
read_cached_record(join_tab);
11257
if (!select || !select->skip_record())
11260
if (!join_tab->check_weed_out_table ||
11261
!(res= do_sj_dups_weedout(join->thd, join_tab->check_weed_out_table)))
11263
rc= (join_tab->next_select)(join,join_tab+1,0);
11264
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11266
reset_cache_write(&join_tab->cache);
11271
return NESTED_LOOP_ERROR;
11275
} while (!(error=info->read_record(info)));
11278
read_cached_record(join_tab); // Restore current record
11279
reset_cache_write(&join_tab->cache);
11280
if (error > 0) // Fatal error
11281
return NESTED_LOOP_ERROR; /* purecov: inspected */
11282
for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
11283
tmp2->table->status=tmp2->status;
11284
return NESTED_LOOP_OK;
11287
int safe_index_read(JOIN_TAB *tab)
3350
11290
Table *table= tab->table;
3351
if ((error=table->cursor->index_read_map(table->getInsertRecord(),
11291
if ((error=table->file->index_read_map(table->record[0],
3352
11292
tab->ref.key_buff,
3353
11293
make_prev_keypart_map(tab->ref.key_parts),
3354
11294
HA_READ_KEY_EXACT)))
6305
static void print_table_array(Session *session, String *str, TableList **table,
15366
/** Allocate memory needed for other rollup functions. */
15368
bool JOIN::rollup_init()
15373
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
15374
rollup.state= ROLLUP::STATE_INITED;
15377
Create pointers to the different sum function groups
15378
These are updated by rollup_make_fields()
15380
tmp_table_param.group_parts= send_group_parts;
15382
if (!(rollup.null_items= (Item_null_result**) thd->alloc((sizeof(Item*) +
15384
sizeof(List<Item>) +
15385
ref_pointer_array_size)
15386
* send_group_parts )))
15389
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
15390
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
15391
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
15394
Prepare space for field list for the different levels
15395
These will be filled up in rollup_make_fields()
15397
for (i= 0 ; i < send_group_parts ; i++)
15399
rollup.null_items[i]= new (thd->mem_root) Item_null_result();
15400
List<Item> *rollup_fields= &rollup.fields[i];
15401
rollup_fields->empty();
15402
rollup.ref_pointer_arrays[i]= ref_array;
15403
ref_array+= all_fields.elements;
15405
for (i= 0 ; i < send_group_parts; i++)
15407
for (j=0 ; j < fields_list.elements ; j++)
15408
rollup.fields[i].push_back(rollup.null_items[i]);
15410
List_iterator<Item> it(all_fields);
15412
while ((item= it++))
15414
order_st *group_tmp;
15415
bool found_in_group= 0;
15417
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
15419
if (*group_tmp->item == item)
15421
item->maybe_null= 1;
15423
if (item->const_item())
15426
For ROLLUP queries each constant item referenced in GROUP BY list
15427
is wrapped up into an Item_func object yielding the same value
15428
as the constant item. The objects of the wrapper class are never
15429
considered as constant items and besides they inherit all
15430
properties of the Item_result_field class.
15431
This wrapping allows us to ensure writing constant items
15432
into temporary tables whenever the result of the ROLLUP
15433
operation has to be written into a temporary table, e.g. when
15434
ROLLUP is used together with DISTINCT in the SELECT list.
15435
Usually when creating temporary tables for a intermidiate
15436
result we do not include fields for constant expressions.
15438
Item* new_item= new Item_func_rollup_const(item);
15441
new_item->fix_fields(thd, (Item **) 0);
15442
thd->change_item_tree(it.ref(), new_item);
15443
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
15445
if (*tmp->item == item)
15446
thd->change_item_tree(tmp->item, new_item);
15451
if (item->type() == Item::FUNC_ITEM && !found_in_group)
15453
bool changed= false;
15454
if (change_group_ref(thd, (Item_func *) item, group_list, &changed))
15457
We have to prevent creation of a field in a temporary table for
15458
an expression that contains GROUP BY attributes.
15459
Marking the expression item as 'with_sum_func' will ensure this.
15462
item->with_sum_func= 1;
15470
Fill up rollup structures with pointers to fields to use.
15472
Creates copies of item_sum items for each sum level.
15474
@param fields_arg List of all fields (hidden and real ones)
15475
@param sel_fields Pointer to selected fields
15476
@param func Store here a pointer to all fields
15480
In this case func is pointing to next not used element.
15485
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields,
15488
List_iterator_fast<Item> it(fields_arg);
15489
Item *first_field= sel_fields.head();
15493
Create field lists for the different levels
15495
The idea here is to have a separate field list for each rollup level to
15496
avoid all runtime checks of which columns should be NULL.
15498
The list is stored in reverse order to get sum function in such an order
15499
in func that it makes it easy to reset them with init_sum_functions()
15501
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15503
rollup.fields[0] will contain list where a,b,c is NULL
15504
rollup.fields[1] will contain list where b,c is NULL
15506
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
15508
sum_funcs_end[0] points to all sum functions
15509
sum_funcs_end[1] points to all sum functions, except grand totals
15513
for (level=0 ; level < send_group_parts ; level++)
15516
uint32_t pos= send_group_parts - level -1;
15517
bool real_fields= 0;
15519
List_iterator<Item> new_it(rollup.fields[pos]);
15520
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
15521
order_st *start_group;
15523
/* Point to first hidden field */
15524
Item **ref_array= ref_array_start + fields_arg.elements-1;
15526
/* Remember where the sum functions ends for the previous level */
15527
sum_funcs_end[pos+1]= *func;
15529
/* Find the start of the group for this level */
15530
for (i= 0, start_group= group_list ;
15532
start_group= start_group->next)
15536
while ((item= it++))
15538
if (item == first_field)
15540
real_fields= 1; // End of hidden fields
15541
ref_array= ref_array_start;
15544
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
15545
(!((Item_sum*) item)->depended_from() ||
15546
((Item_sum *)item)->depended_from() == select_lex))
15550
This is a top level summary function that must be replaced with
15551
a sum function that is reset for this level.
15553
NOTE: This code creates an object which is not that nice in a
15554
sub select. Fortunately it's not common to have rollup in
15557
item= item->copy_or_same(thd);
15558
((Item_sum*) item)->make_unique();
15559
*(*func)= (Item_sum*) item;
15564
/* Check if this is something that is part of this group by */
15565
order_st *group_tmp;
15566
for (group_tmp= start_group, i= pos ;
15567
group_tmp ; group_tmp= group_tmp->next, i++)
15569
if (*group_tmp->item == item)
15572
This is an element that is used by the GROUP BY and should be
15573
set to NULL in this level
15575
Item_null_result *null_item= new (thd->mem_root) Item_null_result();
15578
item->maybe_null= 1; // Value will be null sometimes
15579
null_item->result_field= item->get_tmp_table_field();
15588
(void) new_it++; // Point to next item
15589
new_it.replace(item); // Replace previous
15596
sum_funcs_end[0]= *func; // Point to last function
15601
Send all rollup levels higher than the current one to the client.
15605
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15608
@param idx Level we are on:
15609
- 0 = Total sum level
15610
- 1 = First group changed (a)
15611
- 2 = Second group changed (a,b)
15616
1 If send_data_failed()
15619
int JOIN::rollup_send_data(uint32_t idx)
15622
for (i= send_group_parts ; i-- > idx ; )
15624
/* Get reference pointers to sum functions in place */
15625
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15626
ref_pointer_array_size);
15627
if ((!having || having->val_int()))
15629
if (send_records < unit->select_limit_cnt && do_send_rows &&
15630
result->send_data(rollup.fields[i]))
15635
/* Restore ref_pointer_array */
15636
set_items_ref_array(current_ref_pointer_array);
15641
Write all rollup levels higher than the current one to a temp table.
15645
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
15648
@param idx Level we are on:
15649
- 0 = Total sum level
15650
- 1 = First group changed (a)
15651
- 2 = Second group changed (a,b)
15652
@param table reference to temp table
15657
1 if write_data_failed()
15660
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
15663
for (i= send_group_parts ; i-- > idx ; )
15665
/* Get reference pointers to sum functions in place */
15666
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15667
ref_pointer_array_size);
15668
if ((!having || having->val_int()))
15672
List_iterator_fast<Item> it(rollup.fields[i]);
15673
while ((item= it++))
15675
if (item->type() == Item::NULL_ITEM && item->is_result_field())
15676
item->save_in_result_field(1);
15678
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
15679
if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
15681
if (create_myisam_from_heap(thd, table_arg,
15682
tmp_table_param.start_recinfo,
15683
&tmp_table_param.recinfo,
15689
/* Restore ref_pointer_array */
15690
set_items_ref_array(current_ref_pointer_array);
15695
clear results if there are not rows found for group
15696
(end_send_group/end_write_group)
15701
clear_tables(this);
15702
copy_fields(&tmp_table_param);
15706
Item_sum *func, **func_ptr= sum_funcs;
15707
while ((func= *(func_ptr++)))
15715
Send a description about what how the select will be done to stdout.
15718
void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
15719
bool distinct,const char *message)
15721
List<Item> field_list;
15722
List<Item> item_list;
15723
THD *thd=join->thd;
15724
select_result *result=join->result;
15725
Item *item_null= new Item_null();
15726
const CHARSET_INFO * const cs= system_charset_info;
15728
/* Don't log this into the slow query log */
15729
thd->server_status&= ~(SERVER_QUERY_NO_INDEX_USED | SERVER_QUERY_NO_GOOD_INDEX_USED);
15730
join->unit->offset_limit_cnt= 0;
15733
NOTE: the number/types of items pushed into item_list must be in sync with
15734
EXPLAIN column types as they're "defined" in THD::send_explain_fields()
15738
item_list.push_back(new Item_int((int32_t)
15739
join->select_lex->select_number));
15740
item_list.push_back(new Item_string(join->select_lex->type,
15741
strlen(join->select_lex->type), cs));
15742
for (uint32_t i=0 ; i < 7; i++)
15743
item_list.push_back(item_null);
15744
if (join->thd->lex->describe & DESCRIBE_EXTENDED)
15745
item_list.push_back(item_null);
15747
item_list.push_back(new Item_string(message,strlen(message),cs));
15748
if (result->send_data(item_list))
15751
else if (join->select_lex == join->unit->fake_select_lex)
15754
here we assume that the query will return at least two rows, so we
15755
show "filesort" in EXPLAIN. Of course, sometimes we'll be wrong
15756
and no filesort will be actually done, but executing all selects in
15757
the UNION to provide precise EXPLAIN information will hardly be
15760
char table_name_buffer[NAME_LEN];
15763
item_list.push_back(new Item_null);
15765
item_list.push_back(new Item_string(join->select_lex->type,
15766
strlen(join->select_lex->type),
15770
SELECT_LEX *sl= join->unit->first_select();
15771
uint32_t len= 6, lastop= 0;
15772
memcpy(table_name_buffer, STRING_WITH_LEN("<union"));
15773
for (; sl && len + lastop + 5 < NAME_LEN; sl= sl->next_select())
15776
lastop= snprintf(table_name_buffer + len, NAME_LEN - len,
15777
"%u,", sl->select_number);
15779
if (sl || len + lastop >= NAME_LEN)
15781
memcpy(table_name_buffer + len, STRING_WITH_LEN("...>") + 1);
15787
table_name_buffer[len - 1]= '>'; // change ',' to '>'
15789
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15792
item_list.push_back(new Item_string(join_type_str[JT_ALL],
15793
strlen(join_type_str[JT_ALL]),
15795
/* possible_keys */
15796
item_list.push_back(item_null);
15798
item_list.push_back(item_null);
15800
item_list.push_back(item_null);
15802
item_list.push_back(item_null);
15804
if (join->thd->lex->describe & DESCRIBE_EXTENDED)
15805
item_list.push_back(item_null);
15807
item_list.push_back(item_null);
15809
if (join->unit->global_parameters->order_list.first)
15810
item_list.push_back(new Item_string("Using filesort",
15813
item_list.push_back(new Item_string("", 0, cs));
15815
if (result->send_data(item_list))
15820
table_map used_tables=0;
15821
for (uint32_t i=0 ; i < join->tables ; i++)
15823
JOIN_TAB *tab=join->join_tab+i;
15824
Table *table=tab->table;
15825
TableList *table_list= tab->table->pos_in_table_list;
15827
char buff1[512], buff2[512], buff3[512];
15828
char keylen_str_buf[64];
15829
String extra(buff, sizeof(buff),cs);
15830
char table_name_buffer[NAME_LEN];
15831
String tmp1(buff1,sizeof(buff1),cs);
15832
String tmp2(buff2,sizeof(buff2),cs);
15833
String tmp3(buff3,sizeof(buff3),cs);
15842
item_list.push_back(new Item_uint((uint32_t)
15843
join->select_lex->select_number));
15845
item_list.push_back(new Item_string(join->select_lex->type,
15846
strlen(join->select_lex->type),
15848
if (tab->type == JT_ALL && tab->select && tab->select->quick)
15850
quick_type= tab->select->quick->get_type();
15851
if ((quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) ||
15852
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
15853
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION))
15854
tab->type = JT_INDEX_MERGE;
15856
tab->type = JT_RANGE;
15859
if (table->derived_select_number)
15861
/* Derived table name generation */
15862
int len= snprintf(table_name_buffer, sizeof(table_name_buffer)-1,
15864
table->derived_select_number);
15865
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15869
TableList *real_table= table->pos_in_table_list;
15870
item_list.push_back(new Item_string(real_table->alias,
15871
strlen(real_table->alias),
15874
/* "type" column */
15875
item_list.push_back(new Item_string(join_type_str[tab->type],
15876
strlen(join_type_str[tab->type]),
15878
/* Build "possible_keys" value and add it to item_list */
15879
if (!tab->keys.is_clear_all())
15882
for (j=0 ; j < table->s->keys ; j++)
15884
if (tab->keys.is_set(j))
15888
tmp1.append(table->key_info[j].name,
15889
strlen(table->key_info[j].name),
15890
system_charset_info);
15895
item_list.push_back(new Item_string(tmp1.ptr(),tmp1.length(),cs));
15897
item_list.push_back(item_null);
15899
/* Build "key", "key_len", and "ref" values and add them to item_list */
15900
if (tab->ref.key_parts)
15902
KEY *key_info=table->key_info+ tab->ref.key;
15903
register uint32_t length;
15904
item_list.push_back(new Item_string(key_info->name,
15905
strlen(key_info->name),
15906
system_charset_info));
15907
length= int64_t2str(tab->ref.key_length, keylen_str_buf, 10) -
15909
item_list.push_back(new Item_string(keylen_str_buf, length,
15910
system_charset_info));
15911
for (store_key **ref=tab->ref.key_copy ; *ref ; ref++)
15915
tmp2.append((*ref)->name(), strlen((*ref)->name()),
15916
system_charset_info);
15918
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15920
else if (tab->type == JT_NEXT)
15922
KEY *key_info=table->key_info+ tab->index;
15923
register uint32_t length;
15924
item_list.push_back(new Item_string(key_info->name,
15925
strlen(key_info->name),cs));
15926
length= int64_t2str(key_info->key_length, keylen_str_buf, 10) -
15928
item_list.push_back(new Item_string(keylen_str_buf,
15930
system_charset_info));
15931
item_list.push_back(item_null);
15933
else if (tab->select && tab->select->quick)
15935
tab->select->quick->add_keys_and_lengths(&tmp2, &tmp3);
15936
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15937
item_list.push_back(new Item_string(tmp3.ptr(),tmp3.length(),cs));
15938
item_list.push_back(item_null);
15942
if (table_list->schema_table && table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
15944
const char *tmp_buff;
15946
if (table_list->has_db_lookup_value)
15948
f_idx= table_list->schema_table->idx_field1;
15949
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15950
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15952
if (table_list->has_table_lookup_value)
15954
if (table_list->has_db_lookup_value)
15956
f_idx= table_list->schema_table->idx_field2;
15957
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15958
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15961
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15963
item_list.push_back(item_null);
15966
item_list.push_back(item_null);
15967
item_list.push_back(item_null);
15968
item_list.push_back(item_null);
15971
/* Add "rows" field to item_list. */
15972
if (table_list->schema_table)
15975
if (join->thd->lex->describe & DESCRIBE_EXTENDED)
15976
item_list.push_back(item_null);
15978
item_list.push_back(item_null);
15982
double examined_rows;
15983
if (tab->select && tab->select->quick)
15984
examined_rows= rows2double(tab->select->quick->records);
15985
else if (tab->type == JT_NEXT || tab->type == JT_ALL)
15986
examined_rows= rows2double(tab->limit ? tab->limit :
15987
tab->table->file->records());
15989
examined_rows= join->best_positions[i].records_read;
15991
item_list.push_back(new Item_int((int64_t) (uint64_t) examined_rows,
15992
MY_INT64_NUM_DECIMAL_DIGITS));
15994
/* Add "filtered" field to item_list. */
15995
if (join->thd->lex->describe & DESCRIBE_EXTENDED)
15999
f= (float) (100.0 * join->best_positions[i].records_read /
16001
item_list.push_back(new Item_float(f, 2));
16005
/* Build "Extra" field and add it to item_list. */
16006
bool key_read=table->key_read;
16007
if ((tab->type == JT_NEXT || tab->type == JT_CONST) &&
16008
table->covering_keys.is_set(tab->index))
16010
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT &&
16011
!((QUICK_ROR_INTERSECT_SELECT*)tab->select->quick)->need_to_fetch_row)
16015
item_list.push_back(new Item_string(tab->info,strlen(tab->info),cs));
16016
else if (tab->packed_info & TAB_INFO_HAVE_VALUE)
16018
if (tab->packed_info & TAB_INFO_USING_INDEX)
16019
extra.append(STRING_WITH_LEN("; Using index"));
16020
if (tab->packed_info & TAB_INFO_USING_WHERE)
16021
extra.append(STRING_WITH_LEN("; Using where"));
16022
if (tab->packed_info & TAB_INFO_FULL_SCAN_ON_NULL)
16023
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16024
/* Skip initial "; "*/
16025
const char *str= extra.ptr();
16026
uint32_t len= extra.length();
16032
item_list.push_back(new Item_string(str, len, cs));
16036
uint32_t keyno= MAX_KEY;
16037
if (tab->ref.key_parts)
16038
keyno= tab->ref.key;
16039
else if (tab->select && tab->select->quick)
16040
keyno = tab->select->quick->index;
16042
if (keyno != MAX_KEY && keyno == table->file->pushed_idx_cond_keyno &&
16043
table->file->pushed_idx_cond)
16044
extra.append(STRING_WITH_LEN("; Using index condition"));
16046
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
16047
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
16048
quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE)
16050
extra.append(STRING_WITH_LEN("; Using "));
16051
tab->select->quick->add_info_string(&extra);
16055
if (tab->use_quick == 2)
16057
/* 4 bits per 1 hex digit + terminating '\0' */
16058
char buf[MAX_KEY / 4 + 1];
16059
extra.append(STRING_WITH_LEN("; Range checked for each "
16060
"record (index map: 0x"));
16061
extra.append(tab->keys.print(buf));
16064
else if (tab->select->cond)
16066
const COND *pushed_cond= tab->table->file->pushed_cond;
16068
if (thd->variables.engine_condition_pushdown && pushed_cond)
16070
extra.append(STRING_WITH_LEN("; Using where with pushed "
16072
if (thd->lex->describe & DESCRIBE_EXTENDED)
16074
extra.append(STRING_WITH_LEN(": "));
16075
((COND *)pushed_cond)->print(&extra, QT_ORDINARY);
16079
extra.append(STRING_WITH_LEN("; Using where"));
16084
if (quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
16085
extra.append(STRING_WITH_LEN("; Using index for group-by"));
16087
extra.append(STRING_WITH_LEN("; Using index"));
16089
if (table->reginfo.not_exists_optimize)
16090
extra.append(STRING_WITH_LEN("; Not exists"));
16092
if (quick_type == QUICK_SELECT_I::QS_TYPE_RANGE &&
16093
!(((QUICK_RANGE_SELECT*)(tab->select->quick))->mrr_flags &
16094
HA_MRR_USE_DEFAULT_IMPL))
16096
extra.append(STRING_WITH_LEN("; Using MRR"));
16099
if (table_list->schema_table &&
16100
table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
16102
if (!table_list->table_open_method)
16103
extra.append(STRING_WITH_LEN("; Skip_open_table"));
16104
else if (table_list->table_open_method == OPEN_FRM_ONLY)
16105
extra.append(STRING_WITH_LEN("; Open_frm_only"));
16107
extra.append(STRING_WITH_LEN("; Open_full_table"));
16108
if (table_list->has_db_lookup_value &&
16109
table_list->has_table_lookup_value)
16110
extra.append(STRING_WITH_LEN("; Scanned 0 databases"));
16111
else if (table_list->has_db_lookup_value ||
16112
table_list->has_table_lookup_value)
16113
extra.append(STRING_WITH_LEN("; Scanned 1 database"));
16115
extra.append(STRING_WITH_LEN("; Scanned all databases"));
16117
if (need_tmp_table)
16120
extra.append(STRING_WITH_LEN("; Using temporary"));
16125
extra.append(STRING_WITH_LEN("; Using filesort"));
16127
if (distinct & test_all_bits(used_tables,thd->used_tables))
16128
extra.append(STRING_WITH_LEN("; Distinct"));
16130
if (tab->insideout_match_tab)
16132
extra.append(STRING_WITH_LEN("; LooseScan"));
16135
if (tab->flush_weedout_table)
16136
extra.append(STRING_WITH_LEN("; Start temporary"));
16137
else if (tab->check_weed_out_table)
16138
extra.append(STRING_WITH_LEN("; End temporary"));
16139
else if (tab->do_firstmatch)
16141
extra.append(STRING_WITH_LEN("; FirstMatch("));
16142
Table *prev_table=tab->do_firstmatch->table;
16143
if (prev_table->derived_select_number)
16145
char namebuf[NAME_LEN];
16146
/* Derived table name generation */
16147
int len= snprintf(namebuf, sizeof(namebuf)-1,
16149
prev_table->derived_select_number);
16150
extra.append(namebuf, len);
16153
extra.append(prev_table->pos_in_table_list->alias);
16154
extra.append(STRING_WITH_LEN(")"));
16157
for (uint32_t part= 0; part < tab->ref.key_parts; part++)
16159
if (tab->ref.cond_guards[part])
16161
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16166
if (i > 0 && tab[-1].next_select == sub_select_cache)
16167
extra.append(STRING_WITH_LEN("; Using join buffer"));
16169
/* Skip initial "; "*/
16170
const char *str= extra.ptr();
16171
uint32_t len= extra.length();
16177
item_list.push_back(new Item_string(str, len, cs));
16179
// For next iteration
16180
used_tables|=table->map;
16181
if (result->send_data(item_list))
16185
for (SELECT_LEX_UNIT *unit= join->select_lex->first_inner_unit();
16187
unit= unit->next_unit())
16189
if (mysql_explain_union(thd, unit, result))
16196
bool mysql_explain_union(THD *thd, SELECT_LEX_UNIT *unit, select_result *result)
16199
SELECT_LEX *first= unit->first_select();
16201
for (SELECT_LEX *sl= first;
16203
sl= sl->next_select())
16205
// drop UNCACHEABLE_EXPLAIN, because it is for internal usage only
16206
uint8_t uncacheable= (sl->uncacheable & ~UNCACHEABLE_EXPLAIN);
16207
sl->type= (((&thd->lex->select_lex)==sl)?
16208
(sl->first_inner_unit() || sl->next_select() ?
16209
"PRIMARY" : "SIMPLE"):
16211
((sl->linkage == DERIVED_TABLE_TYPE) ?
16213
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16214
"DEPENDENT SUBQUERY":
16215
(uncacheable?"UNCACHEABLE SUBQUERY":
16217
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16219
uncacheable?"UNCACHEABLE UNION":
16221
sl->options|= SELECT_DESCRIBE;
16223
if (unit->is_union())
16225
unit->fake_select_lex->select_number= UINT_MAX; // jost for initialization
16226
unit->fake_select_lex->type= "UNION RESULT";
16227
unit->fake_select_lex->options|= SELECT_DESCRIBE;
16228
if (!(res= unit->prepare(thd, result, SELECT_NO_UNLOCK | SELECT_DESCRIBE)))
16230
res|= unit->cleanup();
16234
thd->lex->current_select= first;
16235
unit->set_limit(unit->global_parameters);
16236
res= mysql_select(thd, &first->ref_pointer_array,
16237
(TableList*) first->table_list.first,
16238
first->with_wild, first->item_list,
16240
first->order_list.elements +
16241
first->group_list.elements,
16242
(order_st*) first->order_list.first,
16243
(order_st*) first->group_list.first,
16245
(order_st*) thd->lex->proc_list.first,
16246
first->options | thd->options | SELECT_DESCRIBE,
16247
result, unit, first);
16249
return(res || thd->is_error());
16253
static void print_table_array(THD *thd, String *str, TableList **table,
6306
16254
TableList **end)
6308
(*table)->print(session, str, QT_ORDINARY);
16256
(*table)->print(thd, str, QT_ORDINARY);
6310
16258
for (TableList **tbl= table + 1; tbl < end; tbl++)