46
48
#include <drizzled/check_stack_overrun.h>
47
49
#include <drizzled/lock.h>
48
50
#include <drizzled/item/outer_ref.h>
53
#if defined(CMATH_NAMESPACE)
54
using namespace CMATH_NAMESPACE;
57
const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
58
"MAYBE_REF","ALL","range","index",
59
"ref_or_null","unique_subquery","index_subquery",
63
struct st_sargable_param;
65
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
66
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds,
67
DYNAMIC_ARRAY *keyuse);
68
static bool update_ref_and_keys(Session *session, DYNAMIC_ARRAY *keyuse,
70
uint32_t tables, COND *conds,
71
COND_EQUAL *cond_equal,
72
table_map table_map, SELECT_LEX *select_lex,
73
st_sargable_param **sargables);
74
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
75
static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);
76
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
77
table_map used_tables);
78
static bool choose_plan(JOIN *join,table_map join_tables);
80
static void best_access_path(JOIN *join, JOIN_TAB *s, Session *session,
81
table_map remaining_tables, uint32_t idx,
82
double record_count, double read_time);
83
static void optimize_straight_join(JOIN *join, table_map join_tables);
84
static bool greedy_search(JOIN *join, table_map remaining_tables,
85
uint32_t depth, uint32_t prune_level);
86
static bool best_extension_by_limited_search(JOIN *join,
87
table_map remaining_tables,
88
uint32_t idx, double record_count,
89
double read_time, uint32_t depth,
90
uint32_t prune_level);
91
static uint32_t determine_search_depth(JOIN* join);
92
static int join_tab_cmp(const void* ptr1, const void* ptr2);
93
static int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
95
TODO: 'find_best' is here only temporarily until 'greedy_search' is
98
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index,
99
double record_count,double read_time);
100
static uint32_t cache_record_length(JOIN *join,uint32_t index);
101
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
102
static bool get_best_combination(JOIN *join);
103
static store_key *get_store_key(Session *session,
104
KEYUSE *keyuse, table_map used_tables,
105
KEY_PART_INFO *key_part, unsigned char *key_buff,
106
uint32_t maybe_null);
107
static bool make_simple_join(JOIN *join,Table *tmp_table);
108
static void make_outerjoin_info(JOIN *join);
109
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
110
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
111
static bool only_eq_ref_tables(JOIN *join, order_st *order, table_map tables);
112
static void update_depend_map(JOIN *join);
113
static void update_depend_map(JOIN *join, order_st *order);
114
static order_st *remove_const(JOIN *join,order_st *first_order,COND *cond,
115
bool change_list, bool *simple_order);
116
static int return_zero_rows(JOIN *join, select_result *res,TableList *tables,
117
List<Item> &fields, bool send_row,
118
uint64_t select_options, const char *info,
51
#include <drizzled/index_hint.h>
52
#include <drizzled/records.h>
53
#include <drizzled/internal/iocache.h>
54
#include <drizzled/drizzled.h>
55
#include <drizzled/plugin/storage_engine.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>
64
#include <drizzled/filesort.h>
65
#include <drizzled/sql_lex.h>
66
#include <drizzled/session.h>
67
#include <drizzled/sort_field.h>
68
#include <drizzled/select_result.h>
69
#include <drizzled/key.h>
70
#include <drizzled/my_hash.h>
76
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);
120
77
static COND *build_equal_items(Session *session, COND *cond,
121
78
COND_EQUAL *inherited,
122
79
List<TableList> *join_list,
123
80
COND_EQUAL **cond_equal_ref);
124
static COND* substitute_for_best_equal_field(COND *cond,
125
COND_EQUAL *cond_equal,
126
void *table_join_idx);
127
static COND *simplify_joins(JOIN *join, List<TableList> *join_list,
128
COND *conds, bool top, bool in_sj);
129
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
130
static void restore_prev_nj_state(JOIN_TAB *last);
131
static void reset_nj_counters(List<TableList> *join_list);
132
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
133
uint32_t first_unused);
136
void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);
137
static void restore_prev_sj_state(const table_map remaining_tables,
138
const JOIN_TAB *tab);
140
static COND *optimize_cond(JOIN *join, COND *conds,
141
List<TableList> *join_list,
142
Item::cond_result *cond_value);
143
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
144
static int do_select(JOIN *join,List<Item> *fields,Table *tmp_table);
146
static enum_nested_loop_state
147
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
149
static enum_nested_loop_state
150
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
151
static enum_nested_loop_state
152
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
153
static enum_nested_loop_state
154
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
155
static enum_nested_loop_state
156
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
157
static enum_nested_loop_state
158
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
159
static enum_nested_loop_state
160
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
162
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
163
static int join_read_system(JOIN_TAB *tab);
164
static int join_read_const(JOIN_TAB *tab);
165
static int join_read_key(JOIN_TAB *tab);
166
static int join_read_always_key(JOIN_TAB *tab);
167
static int join_read_last_key(JOIN_TAB *tab);
168
static int join_no_more_records(READ_RECORD *info);
169
static int join_read_next(READ_RECORD *info);
170
static int join_read_next_different(READ_RECORD *info);
171
static int join_init_quick_read_record(JOIN_TAB *tab);
172
static int test_if_quick_select(JOIN_TAB *tab);
173
static int join_init_read_record(JOIN_TAB *tab);
174
static int join_read_first(JOIN_TAB *tab);
175
static int join_read_next_same(READ_RECORD *info);
176
static int join_read_next_same_diff(READ_RECORD *info);
177
static int join_read_last(JOIN_TAB *tab);
178
static int join_read_prev_same(READ_RECORD *info);
179
static int join_read_prev(READ_RECORD *info);
180
int join_read_always_key_or_null(JOIN_TAB *tab);
181
int join_read_next_same_or_null(READ_RECORD *info);
182
static COND *make_cond_for_table(COND *cond,table_map table,
183
table_map used_table,
184
bool exclude_expensive_cond);
185
82
static Item* part_of_refkey(Table *form,Field *field);
186
static bool test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,
187
ha_rows select_limit, bool no_changes,
189
static bool list_contains_unique_index(Table *table,
190
bool (*find_func) (Field *, void *), void *data);
191
static bool find_field_in_item_list (Field *field, void *data);
192
static bool find_field_in_order_list (Field *field, void *data);
193
static int create_sort_index(Session *session, JOIN *join, order_st *order,
194
ha_rows filesort_limit, ha_rows select_limit,
196
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields,
198
static int remove_dup_with_compare(Session *session, Table *entry, Field **field,
199
uint32_t offset, Item *having);
200
static int remove_dup_with_hash_index(Session *session,Table *table,
201
uint32_t field_count, Field **first_field,
202
uint32_t key_length, Item *having);
203
static int join_init_cache(Session *session,JOIN_TAB *tables,uint32_t table_count);
204
static uint32_t used_blob_length(CACHE_FIELD **ptr);
205
static bool store_record_in_cache(JOIN_CACHE *cache);
206
static void reset_cache_read(JOIN_CACHE *cache);
207
static void reset_cache_write(JOIN_CACHE *cache);
208
static void read_cached_record(JOIN_TAB *tab);
209
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
210
static order_st *create_distinct_group(Session *session, Item **ref_pointer_array,
211
order_st *order, List<Item> &fields,
212
List<Item> &all_fields,
213
bool *all_order_by_fields_used);
214
static bool test_if_subpart(order_st *a,order_st *b);
215
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
216
static void calc_group_buffer(JOIN *join,order_st *group);
217
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
218
static bool alloc_group_fields(JOIN *join,order_st *group);
219
// Create list for using with tempory table
220
static bool change_to_use_tmp_fields(Session *session, Item **ref_pointer_array,
221
List<Item> &new_list1,
222
List<Item> &new_list2,
223
uint32_t elements, List<Item> &items);
224
// Create list for using with tempory table
225
static bool change_refs_to_tmp_fields(Session *session, Item **ref_pointer_array,
226
List<Item> &new_list1,
227
List<Item> &new_list2,
228
uint32_t elements, List<Item> &items);
229
static void init_tmptable_sum_functions(Item_sum **func);
230
static void update_tmptable_sum_func(Item_sum **func,Table *tmp_table);
231
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
232
static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab);
233
static bool setup_sum_funcs(Session *session, Item_sum **func_ptr);
234
static bool init_sum_functions(Item_sum **func, Item_sum **end);
235
static bool update_sum_func(Item_sum **func);
236
void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
237
bool distinct, const char *message=NULL);
238
static Item *remove_additional_cond(Item* conds);
239
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
240
static bool test_if_ref(Item_field *left_item,Item *right_item);
241
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
242
Item *new_cond, bool fix_fields);
83
static bool cmp_buffer_with_ref(JoinTable *tab);
84
static void change_cond_ref_to_const(Session *session,
85
list<COND_CMP>& save_list,
90
static void copy_blobs(Field **ptr);
244
92
static bool eval_const_cond(COND *cond)
246
return ((Item_func*) cond)->val_int() ? true : false;
94
return ((Item_func*) cond)->val_int() ? true : false;
251
98
This is used to mark equalities that were made from i-th IN-equality.
252
99
We limit semi-join InsideOut optimization to handling max 64 inequalities,
253
100
The following variable occupies 64 addresses.
255
const char *subq_sj_cond_name=
256
"0123456789ABCDEF0123456789abcdef0123456789ABCDEF0123456789abcdef-sj-cond";
102
const char *subq_sj_cond_name= "0123456789ABCDEF0123456789abcdef0123456789ABCDEF0123456789abcdef-sj-cond";
258
static bool bitmap_covers(const table_map x, const table_map y)
104
static void copy_blobs(Field **ptr)
260
return !test(y & ~x);
108
if ((*ptr)->flags & BLOB_FLAG)
110
((Field_blob *) (*ptr))->copy();
264
116
This handles SELECT with and without UNION.
267
118
bool handle_select(Session *session, LEX *lex, select_result *result,
268
ulong setup_tables_done_option)
119
uint64_t setup_tables_done_option)
271
register SELECT_LEX *select_lex = &lex->select_lex;
272
DRIZZLE_SELECT_START();
122
Select_Lex *select_lex= &lex->select_lex;
123
DRIZZLE_SELECT_START(session->getQueryString()->c_str());
274
if (select_lex->master_unit()->is_union() ||
125
if (select_lex->master_unit()->is_union() or
275
126
select_lex->master_unit()->fake_select_lex)
276
res= mysql_union(session, lex, result, &lex->unit, setup_tables_done_option);
128
res= drizzle_union(session, lex, result, &lex->unit,
129
setup_tables_done_option);
279
SELECT_LEX_UNIT *unit= &lex->unit;
133
Select_Lex_Unit *unit= &lex->unit;
280
134
unit->set_limit(unit->global_parameters);
281
135
session->session_marker= 0;
283
'options' of mysql_select will be set in JOIN, as far as JOIN for
138
'options' of select_query will be set in JOIN, as far as JOIN for
284
139
every PS/SP execution new, we will not need reset this flag if
285
140
setup_tables_done_option changed for next rexecution
287
res= mysql_select(session, &select_lex->ref_pointer_array,
142
res= select_query(session,
143
&select_lex->ref_pointer_array,
288
144
(TableList*) select_lex->table_list.first,
289
select_lex->with_wild, select_lex->item_list,
145
select_lex->with_wild,
146
select_lex->item_list,
290
147
select_lex->where,
291
select_lex->order_list.elements +
292
select_lex->group_list.elements,
293
(order_st*) select_lex->order_list.first,
294
(order_st*) select_lex->group_list.first,
148
select_lex->order_list.size() +
149
select_lex->group_list.size(),
150
(Order*) select_lex->order_list.first,
151
(Order*) select_lex->group_list.first,
295
152
select_lex->having,
296
(order_st*) lex->proc_list.first,
297
153
select_lex->options | session->options |
298
154
setup_tables_done_option,
299
155
result, unit, select_lex);
301
157
res|= session->is_error();
302
159
if (unlikely(res))
305
DRIZZLE_SELECT_END();
164
DRIZZLE_SELECT_DONE(res, session->limit_found_rows);
311
169
Fix fields referenced from inner selects.
403
265
new_ref= direct_ref ?
404
266
new Item_direct_ref(ref->context, item_ref, ref->table_name,
405
267
ref->field_name, ref->alias_name_used) :
406
268
new Item_ref(ref->context, item_ref, ref->table_name,
407
269
ref->field_name, ref->alias_name_used);
410
271
ref->outer_ref= new_ref;
411
272
ref->ref= &ref->outer_ref;
413
274
if (!ref->fixed && ref->fix_fields(session, 0))
415
278
session->used_tables|= item->used_tables();
421
Function to setup clauses without sum functions.
423
inline int setup_without_group(Session *session, Item **ref_pointer_array,
427
List<Item> &all_fields,
430
order_st *group, bool *hidden_group_fields)
433
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
435
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
436
res= setup_conds(session, tables, leaves, conds);
438
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
439
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
441
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
442
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
443
group, hidden_group_fields);
444
session->lex->allow_sum_func= save_allow_sum_func;
448
283
/*****************************************************************************
449
284
Check fields, find best join, do the select and output fields.
450
mysql_select assumes that all tables are already opened
285
select_query assumes that all tables are already opened
451
286
*****************************************************************************/
454
Prepare of whole select (including sub queries in future).
457
Add check of calculation of GROUP functions and fields:
458
SELECT COUNT(*)+table.col1 from table1;
466
JOIN::prepare(Item ***rref_pointer_array,
467
TableList *tables_init,
468
uint32_t wild_num, COND *conds_init, uint32_t og_num,
469
order_st *order_init, order_st *group_init,
471
order_st *proc_param_init, SELECT_LEX *select_lex_arg,
472
SELECT_LEX_UNIT *unit_arg)
474
// to prevent double initialization on EXPLAIN
480
group_list= group_init;
482
proc_param= proc_param_init;
483
tables_list= tables_init;
484
select_lex= select_lex_arg;
485
select_lex->join= this;
486
join_list= &select_lex->top_join_list;
487
union_part= unit_arg->is_union();
489
session->lex->current_select->is_item_list_lookup= 1;
491
If we have already executed SELECT, then it have not sense to prevent
492
its table from update (see unique_table())
494
if (session->derived_tables_processing)
495
select_lex->exclude_from_table_unique_test= true;
497
/* Check that all tables, fields, conds and order are ok */
499
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
500
setup_tables_and_check_access(session, &select_lex->context, join_list,
501
tables_list, &select_lex->leaf_tables,
505
TableList *table_ptr;
506
for (table_ptr= select_lex->leaf_tables;
508
table_ptr= table_ptr->next_leaf)
511
if (setup_wild(session, tables_list, fields_list, &all_fields, wild_num) ||
512
select_lex->setup_ref_array(session, og_num) ||
513
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
515
setup_without_group(session, (*rref_pointer_array), tables_list,
516
select_lex->leaf_tables, fields_list,
517
all_fields, &conds, order, group_list,
518
&hidden_group_fields))
519
return(-1); /* purecov: inspected */
521
ref_pointer_array= *rref_pointer_array;
525
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
526
session->where="having clause";
527
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
528
select_lex->having_fix_field= 1;
529
bool having_fix_rc= (!having->fixed &&
530
(having->fix_fields(session, &having) ||
531
having->check_cols(1)));
532
select_lex->having_fix_field= 0;
533
if (having_fix_rc || session->is_error())
534
return(-1); /* purecov: inspected */
535
session->lex->allow_sum_func= save_allow_sum_func;
539
Item_subselect *subselect;
540
Item_in_subselect *in_subs= NULL;
542
Are we in a subquery predicate?
543
TODO: the block below will be executed for every PS execution without need.
545
if ((subselect= select_lex->master_unit()->item))
547
bool do_semijoin= !test(session->variables.optimizer_switch &
548
OPTIMIZER_SWITCH_NO_SEMIJOIN);
549
if (subselect->substype() == Item_subselect::IN_SUBS)
550
in_subs= (Item_in_subselect*)subselect;
553
Check if we're in subquery that is a candidate for flattening into a
554
semi-join (which is done done in flatten_subqueries()). The
556
1. Subquery predicate is an IN/=ANY subq predicate
557
2. Subquery is a single SELECT (not a UNION)
558
3. Subquery does not have GROUP BY or order_st BY
559
4. Subquery does not use aggregate functions or HAVING
560
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
561
6. No execution method was already chosen (by a prepared statement).
563
(*). We are not in a subquery of a single table UPDATE/DELETE that
564
doesn't have a JOIN (TODO: We should handle this at some
565
point by switching to multi-table UPDATE/DELETE)
567
(**). We're not in a confluent table-less subquery, like
571
!select_lex->master_unit()->first_select()->next_select() && // 2
572
!select_lex->group_list.elements && !order && // 3
573
!having && !select_lex->with_sum_func && // 4
574
session->session_marker && // 5
575
select_lex->outer_select()->join && // (*)
576
select_lex->master_unit()->first_select()->leaf_tables && // (**)
578
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
581
if (!in_subs->left_expr->fixed &&
582
in_subs->left_expr->fix_fields(session, &in_subs->left_expr))
587
Check that the right part of the subselect contains no more than one
588
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
590
if (subselect->substype() == Item_subselect::IN_SUBS &&
591
(select_lex->item_list.elements !=
592
((Item_in_subselect*)subselect)->left_expr->cols()))
594
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
599
/* Register the subquery for further processing */
600
select_lex->outer_select()->join->sj_subselects.append(session->mem_root, in_subs);
601
in_subs->expr_join_nest= (TableList*)session->session_marker;
605
bool do_materialize= !test(session->variables.optimizer_switch &
606
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
608
Check if the subquery predicate can be executed via materialization.
609
The required conditions are:
610
1. Subquery predicate is an IN/=ANY subq predicate
611
2. Subquery is a single SELECT (not a UNION)
612
3. Subquery is not a table-less query. In this case there is no
613
point in materializing.
614
4. Subquery predicate is a top-level predicate
615
(this implies it is not negated)
616
TODO: this is a limitation that should be lifeted once we
617
implement correct NULL semantics (WL#3830)
618
5. Subquery is non-correlated
620
This is an overly restrictive condition. It can be extended to:
621
(Subquery is non-correlated ||
622
Subquery is correlated to any query outer to IN predicate ||
623
(Subquery is correlated to the immediate outer query &&
624
Subquery !contains {GROUP BY, order_st BY [LIMIT],
625
aggregate functions) && subquery predicate is not under "NOT IN"))
626
6. No execution method was already chosen (by a prepared statement).
628
(*) The subquery must be part of a SELECT statement. The current
629
condition also excludes multi-table update statements.
631
We have to determine whether we will perform subquery materialization
632
before calling the IN=>EXISTS transformation, so that we know whether to
633
perform the whole transformation or only that part of it which wraps
634
Item_in_subselect in an Item_in_optimizer.
636
if (do_materialize &&
638
!select_lex->master_unit()->first_select()->next_select() && // 2
639
select_lex->master_unit()->first_select()->leaf_tables && // 3
640
session->lex->sql_command == SQLCOM_SELECT) // *
642
if (in_subs->is_top_level_item() && // 4
643
!in_subs->is_correlated && // 5
644
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
645
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
648
Item_subselect::trans_res trans_res;
649
if ((trans_res= subselect->select_transformer(this)) !=
650
Item_subselect::RES_OK)
652
return((trans_res == Item_subselect::RES_ERROR));
661
for (ord= order; ord; ord= ord->next)
663
Item *item= *ord->item;
664
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
665
item->split_sum_func(session, ref_pointer_array, all_fields);
669
if (having && having->with_sum_func)
670
having->split_sum_func(session, ref_pointer_array, all_fields,
672
if (select_lex->inner_sum_func_list)
674
Item_sum *end=select_lex->inner_sum_func_list;
675
Item_sum *item_sum= end;
678
item_sum= item_sum->next;
679
item_sum->split_sum_func(session, ref_pointer_array,
680
all_fields, item_sum->ref_by, false);
681
} while (item_sum != end);
684
if (select_lex->inner_refs_list.elements &&
685
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
689
Check if there are references to un-aggregated columns when computing
690
aggregate functions with implicit grouping (there is no GROUP BY).
692
MODE_ONLY_FULL_GROUP_BY is enabled here by default
694
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
696
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
697
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
701
/* Caclulate the number of groups */
703
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
708
goto err; /* purecov: inspected */
710
if (result && result->prepare(fields_list, unit_arg))
711
goto err; /* purecov: inspected */
713
/* Init join struct */
714
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
715
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
716
this->group= group_list != 0;
719
#ifdef RESTRICTED_GROUP
720
if (sum_func_count && !group_list && (func_count || field_count))
722
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
726
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
728
if (alloc_func_list())
734
return(-1); /* purecov: inspected */
739
Remove the predicates pushed down into the subquery
742
JOIN::remove_subq_pushed_predicates()
743
where IN Must be NULL
744
OUT The remaining WHERE condition, or NULL
747
Given that this join will be executed using (unique|index)_subquery,
748
without "checking NULL", remove the predicates that were pushed down
751
If the subquery compares scalar values, we can remove the condition that
752
was wrapped into trig_cond (it will be checked when needed by the subquery
755
If the subquery compares row values, we need to keep the wrapped
756
equalities in the WHERE clause: when the left (outer) tuple has both NULL
757
and non-NULL values, we'll do a full table scan and will rely on the
758
equalities corresponding to non-NULL parts of left tuple to filter out
759
non-matching records.
761
TODO: We can remove the equalities that will be guaranteed to be true by the
762
fact that subquery engine will be using index lookup. This must be done only
763
for cases where there are no conversion errors of significance, e.g. 257
764
that is searched in a byte. But this requires homogenization of the return
765
codes of all Field*::store() methods.
768
void JOIN::remove_subq_pushed_predicates(Item **where)
770
if (conds->type() == Item::FUNC_ITEM &&
771
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
772
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
773
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
774
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
775
((Item_func *)conds)->arguments()[0]))
784
289
Index lookup-based subquery: save some flags for EXPLAIN output
823
Check if the table's rowid is included in the temptable
826
sj_table_is_included()
828
join_tab The table to be checked
831
SemiJoinDuplicateElimination: check the table's rowid should be included
832
in the temptable. This is so if
834
1. The table is not embedded within some semi-join nest
835
2. The has been pulled out of a semi-join nest, or
837
3. The table is functionally dependent on some previous table
839
[4. This is also true for constant tables that can't be
840
NULL-complemented but this function is not called for such tables]
843
true - Include table's rowid
847
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
849
if (join_tab->emb_sj_nest)
852
/* Check if this table is functionally dependent on the tables that
853
are within the same outer join nest
855
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
856
if (join_tab->type == JT_EQ_REF)
858
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
860
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
862
JOIN_TAB *ref_tab= join->join_tab + idx;
863
if (embedding == ref_tab->table->pos_in_table_list->embedding)
866
/* Ok, functionally dependent */
869
/* Not functionally dependent => need to include*/
875
Setup the strategies to eliminate semi-join duplicates.
878
setup_semijoin_dups_elimination()
880
options Join options (needed to see if join buffering will be
882
no_jbuf_after Another bit of information re where join buffering will
886
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
889
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
891
2. FirstMatch (pick only the 1st matching row combination of inner tables)
892
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
893
together and picking the 1st one)
895
The join order has "duplicate-generating ranges", and every range is
896
served by one strategy or a combination of FirstMatch with with some
899
"Duplicate-generating range" is defined as a range within the join order
900
that contains all of the inner tables of a semi-join. All ranges must be
901
disjoint, if tables of several semi-joins are interleaved, then the ranges
902
are joined together, which is equivalent to converting
903
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
905
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
908
Applicability conditions are as follows:
910
DuplicateWeedout strategy
911
~~~~~~~~~~~~~~~~~~~~~~~~~
913
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
914
+------+ +=========================+ +---+
917
(1) - Prefix of OuterTables (those that participate in
918
IN-equality and/or are correlated with subquery) and outer
919
Noncorrelated Tables.
920
(2) - The handled range. The range starts with the first sj-inner
921
table, and covers all sj-inner and outer tables
922
Within the range, Inner, Outer, outer Noncorrelated tables
923
may follow in any order.
924
(3) - The suffix of outer Noncorrelated tables.
929
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
930
+------+ +==================+ +---+
933
(1) - Prefix of outer and non-correlated tables
934
(2) - The handled range, which may contain only inner and
935
non-correlated tables.
936
(3) - The suffix of outer Noncorrelated tables.
941
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
942
+--------+ +===========+ +=============+ +------+
945
(1) - Prefix that may contain any outer tables. The prefix must contain
946
all the non-trivially correlated outer tables. (non-trivially means
947
that the correlation is not just through the IN-equality).
949
(2) - Inner table for which the InsideOut scan is performed.
951
(3) - The remainder of the duplicate-generating range. It is served by
952
application of FirstMatch strategy, with the exception that
953
outer IN-correlated tables are considered to be non-correlated.
955
(4) - THe suffix of outer and outer non-correlated tables.
957
If several strategies are applicable, their relative priorities are:
962
This function walks over the join order and sets up the strategies by
963
setting appropriate members in join_tab structures.
967
true Out of memory error
971
int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
973
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
976
0 - invalid (EOF marker),
978
2 - Temptable (maybe confluent),
979
3 - Temptable with join buffering
982
uint32_t start_idx; /* Left range bound */
983
uint32_t end_idx; /* Right range bound */
985
For Temptable strategy: Bitmap of all outer and correlated tables from
986
all involved join nests.
988
table_map outer_tables;
989
} dups_ranges [MAX_TABLES];
991
TableList *emb_insideout_nest= NULL;
992
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
993
tables) whose ranges we're in */
994
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
995
table_map range_start_map= 0; /* table_map at current range start */
996
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
1001
First pass: locate the duplicate-generating ranges and pick the strategies.
1003
for (i=join->const_tables ; i < join->tables ; i++)
1005
JOIN_TAB *tab=join->join_tab+i;
1006
Table *table=tab->table;
1007
cur_map |= table->map;
1009
if (tab->emb_sj_nest) // Encountered an sj-inner table
1013
dups_ranges[cur_range].start_idx= i;
1014
range_start_map= cur_map & ~table->map;
1016
Remember if this is a possible start of range that is covered by
1017
the InsideOut strategy (the reason that it is not covered could
1018
be that it overlaps with anther semi-join's range. we don't
1019
support InsideOut for joined ranges)
1021
if (join->best_positions[i].use_insideout_scan)
1022
emb_insideout_nest= tab->emb_sj_nest;
1025
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
1026
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
1028
if (tab->emb_sj_nest != emb_insideout_nest)
1031
Two different semi-joins interleave. This cannot be handled by
1034
emb_insideout_nest= NULL;
1038
if (emb_sj_map) /* We're in duplicate-generating range */
1040
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
1041
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
1042
i <= no_jbuf_after && !dealing_with_jbuf)
1045
This table uses join buffering, which makes use of FirstMatch or
1046
InsideOut strategies impossible for the current and (we assume)
1047
preceding duplicate-producing ranges.
1048
That is, for the join order:
1050
x x [ x x] x [x x x] x [x x X* x] x
1052
+-----+ +-----+ | join buffering use
1055
we'll have to remove r1 and r2 and use duplicate-elimination
1056
strategy that spans all the tables, starting from the very 1st
1059
dealing_with_jbuf= true;
1060
emb_insideout_nest= false;
1063
Absorb all preceding duplicate-eliminating ranges. Their strategies
1066
for (int prev_range= 0; prev_range < cur_range; prev_range++)
1068
dups_ranges[cur_range].outer_tables |=
1069
dups_ranges[prev_range].outer_tables;
1071
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
1072
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
1077
Check if we are at the end of duplicate-producing range. We are if
1079
1. It's an InsideOut range (which presumes all correlated tables are
1080
in the prefix), and all inner tables are in the join order prefix,
1082
2. It's a DuplicateElimination range (possibly covering several
1083
SJ-nests), and all inner, outer, and correlated tables of all
1084
sj-nests are in the join order prefix.
1086
bool end_of_range= false;
1087
if (emb_insideout_nest &&
1088
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
1090
/* Save that this range is handled with InsideOut: */
1091
dups_ranges[cur_range].strategy= 1;
1094
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
1097
This is a complete range to be handled with either DuplicateWeedout
1100
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
1102
This will hold tables from within the range that need to be put
1103
into the join buffer before we can use the FirstMatch on its tail.
1105
dups_ranges[cur_range].outer_tables= emb_outer_tables &
1112
dups_ranges[cur_range].end_idx= i+1;
1113
emb_sj_map= emb_outer_tables= 0;
1114
emb_insideout_nest= NULL;
1115
dealing_with_jbuf= false;
1116
dups_ranges[++cur_range].strategy= 0;
1121
Session *session= join->session;
1122
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
1124
Second pass: setup the chosen strategies
1126
for (int j= 0; j < cur_range; j++)
1128
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
1130
if (dups_ranges[j].strategy == 1) // InsideOut strategy
1132
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
1135
else // DuplicateWeedout strategy
1137
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
1138
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
1139
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
1140
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
1141
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
1142
uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
1143
JOIN_TAB *last_outer_tab= tab - 1;
1145
Walk through the range and remember
1146
- tables that need their rowids to be put into temptable
1147
- the last outer table
1149
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1151
if (sj_table_is_included(join, tab))
1153
last_tab->join_tab= tab;
1154
last_tab->rowid_offset= jt_rowid_offset;
1155
jt_rowid_offset += tab->table->file->ref_length;
1156
if (tab->table->maybe_null)
1158
last_tab->null_byte= jt_null_bits / 8;
1159
last_tab->null_bit= jt_null_bits++;
1162
tab->table->prepare_for_position();
1163
tab->rowid_keep_flags= rowid_keep_flags;
1165
cur_map |= tab->table->map;
1166
if (!tab->emb_sj_nest && bitmap_covers(cur_map,
1167
dups_ranges[j].outer_tables))
1168
last_outer_tab= tab;
1171
if (jt_rowid_offset) /* Temptable has at least one rowid */
1173
SJ_TMP_TABLE *sjtbl;
1174
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
1175
if (!(sjtbl= (SJ_TMP_TABLE*)session->alloc(sizeof(SJ_TMP_TABLE))) ||
1176
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) session->alloc(tabs_size)))
1178
memcpy(sjtbl->tabs, sjtabs, tabs_size);
1179
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
1180
sjtbl->rowid_len= jt_rowid_offset;
1181
sjtbl->null_bits= jt_null_bits;
1182
sjtbl->null_bytes= (jt_null_bits + 7)/8;
1184
*next_sjtbl_ptr= sjtbl;
1185
next_sjtbl_ptr= &(sjtbl->next);
1189
create_duplicate_weedout_tmp_table(session,
1194
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
1195
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
1197
tab= last_outer_tab + 1;
1198
jump_to= last_outer_tab;
1201
/* Create the FirstMatch tail */
1202
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1204
if (tab->emb_sj_nest)
1205
tab->do_firstmatch= jump_to;
1214
static void cleanup_sj_tmp_tables(JOIN *join)
1216
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
1217
sj_tbl= sj_tbl->next)
1219
if (sj_tbl->tmp_table)
1221
sj_tbl->tmp_table->free_tmp_table(join->session);
1224
join->sj_tmp_tables= NULL;
1227
uint32_t make_join_orderinfo(JOIN *join);
1230
global select optimisation.
1233
error code saved in field 'error'
1244
// to prevent double initialization on EXPLAIN
1249
session->set_proc_info("optimizing");
1250
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
1251
unit->select_limit_cnt);
1252
/* select_limit is used to decide if we are likely to scan the whole table */
1253
select_limit= unit->select_limit_cnt;
1254
if (having || (select_options & OPTION_FOUND_ROWS))
1255
select_limit= HA_POS_ERROR;
1256
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
1257
// Ignore errors of execution if option IGNORE present
1258
if (session->lex->ignore)
1259
session->lex->current_select->no_error= 1;
1261
#ifdef HAVE_REF_TO_FIELDS // Not done yet
1262
/* Add HAVING to WHERE if possible */
1263
if (having && !group_list && !sum_func_count)
1270
else if ((conds=new Item_cond_and(conds,having)))
1273
Item_cond_and can't be fixed after creation, so we do not check
1276
conds->fix_fields(session, &conds);
1277
conds->change_ref_to_fields(session, tables_list);
1278
conds->top_level_item();
1284
/* Convert all outer joins to inner joins if possible */
1285
conds= simplify_joins(this, join_list, conds, true, false);
1286
build_bitmap_for_nested_joins(join_list, 0);
1288
conds= optimize_cond(this, conds, join_list, &cond_value);
1289
if (session->is_error())
1296
having= optimize_cond(this, having, join_list, &having_value);
1297
if (session->is_error())
1302
if (select_lex->where)
1303
select_lex->cond_value= cond_value;
1304
if (select_lex->having)
1305
select_lex->having_value= having_value;
1307
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
1308
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
1309
{ /* Impossible cond */
1310
zero_result_cause= having_value == Item::COND_FALSE ?
1311
"Impossible HAVING" : "Impossible WHERE";
1317
/* Optimize count(*), cmin() and cmax() */
1318
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
1322
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
1323
to the WHERE conditions,
1324
or 1 if all items were resolved,
1325
or 0, or an error number HA_ERR_...
1327
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
1329
if (res == HA_ERR_KEY_NOT_FOUND)
1331
zero_result_cause= "No matching min/max row";
1342
zero_result_cause= "No matching min/max row";
1346
zero_result_cause= "Select tables optimized away";
1347
tables_list= 0; // All tables resolved
1349
Extract all table-independent conditions and replace the WHERE
1350
clause with them. All other conditions were computed by opt_sum_query
1351
and the MIN/MAX/COUNT function(s) have been replaced by constants,
1352
so there is no need to compute the whole WHERE clause again.
1353
Notice that make_cond_for_table() will always succeed to remove all
1354
computed conditions, because opt_sum_query() is applicable only to
1356
Preserve conditions for EXPLAIN.
1358
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
1360
COND *table_independent_conds=
1361
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
1362
conds= table_independent_conds;
1371
error= -1; // Error is sent to client
1372
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
1374
/* Calculate how to do the join */
1375
session->set_proc_info("statistics");
1376
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
1377
session->is_fatal_error)
1382
/* Remove distinct if only const tables */
1383
select_distinct= select_distinct && (const_tables != tables);
1384
session->set_proc_info("preparing");
1385
if (result->initialize_tables(this))
1387
return(1); // error == -1
1389
if (const_table_map != found_const_table_map &&
1390
!(select_options & SELECT_DESCRIBE) &&
1392
!(conds->used_tables() & RAND_TABLE_BIT) ||
1393
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
1395
zero_result_cause= "no matching row in const table";
1399
if (!(session->options & OPTION_BIG_SELECTS) &&
1400
best_read > (double) session->variables.max_join_size &&
1401
!(select_options & SELECT_DESCRIBE))
1402
{ /* purecov: inspected */
1403
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
1407
if (const_tables && !session->locked_tables &&
1408
!(select_options & SELECT_NO_UNLOCK))
1409
mysql_unlock_some_tables(session, table, const_tables);
1410
if (!conds && outer_join)
1412
/* Handle the case where we have an OUTER JOIN without a WHERE */
1413
conds=new Item_int((int64_t) 1,1); // Always true
1415
select= make_select(*table, const_table_map,
1416
const_table_map, conds, 1, &error);
1418
{ /* purecov: inspected */
1419
error= -1; /* purecov: inspected */
1423
reset_nj_counters(join_list);
1424
make_outerjoin_info(this);
1427
Among the equal fields belonging to the same multiple equality
1428
choose the one that is to be retrieved first and substitute
1429
all references to these in where condition for a reference for
1434
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
1435
conds->update_used_tables();
1439
Permorm the the optimization on fields evaluation mentioned above
1440
for all on expressions.
1442
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
1444
if (*tab->on_expr_ref)
1446
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
1449
(*tab->on_expr_ref)->update_used_tables();
1453
if (conds &&!outer_join && const_table_map != found_const_table_map &&
1454
(select_options & SELECT_DESCRIBE) &&
1455
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
1457
conds=new Item_int((int64_t) 0,1); // Always false
1459
if (make_join_select(this, select, conds))
1462
"Impossible WHERE noticed after reading const tables";
1463
return(0); // error == 0
1466
error= -1; /* if goto err */
1468
/* Optimize distinct away if possible */
1470
order_st *org_order= order;
1471
order=remove_const(this, order,conds,1, &simple_order);
1472
if (session->is_error())
1479
If we are using order_st BY NULL or order_st BY const_expression,
1480
return result in any order (even if we are using a GROUP BY)
1482
if (!order && org_order)
1486
Check if we can optimize away GROUP BY/DISTINCT.
1487
We can do that if there are no aggregate functions, the
1488
fields in DISTINCT clause (if present) and/or columns in GROUP BY
1489
(if present) contain direct references to all key parts of
1490
an unique index (in whatever order) and if the key parts of the
1491
unique index cannot contain NULLs.
1492
Note that the unique keys for DISTINCT and GROUP BY should not
1493
be the same (as long as they are unique).
1495
The FROM clause must contain a single non-constant table.
1497
if (tables - const_tables == 1 && (group_list || select_distinct) &&
1498
!tmp_table_param.sum_func_count &&
1499
(!join_tab[const_tables].select ||
1500
!join_tab[const_tables].select->quick ||
1501
join_tab[const_tables].select->quick->get_type() !=
1502
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
1505
list_contains_unique_index(join_tab[const_tables].table,
1506
find_field_in_order_list,
1507
(void *) group_list))
1510
We have found that grouping can be removed since groups correspond to
1511
only one row anyway, but we still have to guarantee correct result
1512
order. The line below effectively rewrites the query from GROUP BY
1513
<fields> to order_st BY <fields>. There are two exceptions:
1514
- if skip_sort_order is set (see above), then we can simply skip
1516
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
1517
with the GROUP BY ones, i.e. either one is a prefix of another.
1518
We only check if the order_st BY is a prefix of GROUP BY. In this case
1519
test_if_subpart() copies the ASC/DESC attributes from the original
1521
If GROUP BY is a prefix of order_st BY, then it is safe to leave
1524
if (!order || test_if_subpart(group_list, order))
1525
order= skip_sort_order ? 0 : group_list;
1527
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
1528
rewritten to IGNORE INDEX FOR order_st BY(fields).
1530
join_tab->table->keys_in_use_for_order_by=
1531
join_tab->table->keys_in_use_for_group_by;
1535
if (select_distinct &&
1536
list_contains_unique_index(join_tab[const_tables].table,
1537
find_field_in_item_list,
1538
(void *) &fields_list))
1543
if (group_list || tmp_table_param.sum_func_count)
1545
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
1548
else if (select_distinct && tables - const_tables == 1)
1551
We are only using one table. In this case we change DISTINCT to a
1553
- The GROUP BY can be done through indexes (no sort) and the order_st
1554
BY only uses selected fields.
1555
(In this case we can later optimize away GROUP BY and order_st BY)
1556
- We are scanning the whole table without LIMIT
1558
- We are using CALC_FOUND_ROWS
1559
- We are using an order_st BY that can't be optimized away.
1561
We don't want to use this optimization when we are using LIMIT
1562
because in this case we can just create a temporary table that
1563
holds LIMIT rows and stop when this table is full.
1565
JOIN_TAB *tab= &join_tab[const_tables];
1566
bool all_order_fields_used;
1568
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
1569
&tab->table->keys_in_use_for_order_by);
1570
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
1571
order, fields_list, all_fields,
1572
&all_order_fields_used)))
1574
bool skip_group= (skip_sort_order &&
1575
test_if_skip_sort_order(tab, group_list, select_limit, 1,
1576
&tab->table->keys_in_use_for_group_by) != 0);
1577
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
1578
if ((skip_group && all_order_fields_used) ||
1579
select_limit == HA_POS_ERROR ||
1580
(order && !skip_sort_order))
1582
/* Change DISTINCT to GROUP BY */
1585
if (all_order_fields_used)
1587
if (order && skip_sort_order)
1590
Force MySQL to read the table in sorted order to get result in
1593
tmp_table_param.quick_group=0;
1597
group=1; // For end_write_group
1602
else if (session->is_fatal_error) // End of memory
1607
order_st *old_group_list;
1608
group_list= remove_const(this, (old_group_list= group_list), conds,
1609
rollup.state == ROLLUP::STATE_NONE,
1611
if (session->is_error())
1616
if (old_group_list && !group_list)
1619
if (!group_list && group)
1621
order=0; // The output has only one row
1623
select_distinct= 0; // No need in distinct for 1 row
1624
group_optimized_away= 1;
1627
calc_group_buffer(this, group_list);
1628
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
1630
if (test_if_subpart(group_list, order) ||
1631
(!group_list && tmp_table_param.sum_func_count))
1634
// Can't use sort on head table if using row cache
1644
Check if we need to create a temporary table.
1645
This has to be done if all tables are not already read (const tables)
1646
and one of the following conditions holds:
1647
- We are using DISTINCT (simple distinct's are already optimized away)
1648
- We are using an order_st BY or GROUP BY on fields not in the first table
1649
- We are using different order_st BY and GROUP BY orders
1650
- The user wants us to buffer the result.
1652
need_tmp= (const_tables != tables &&
1653
((select_distinct || !simple_order || !simple_group) ||
1654
(group_list && order) ||
1655
test(select_options & OPTION_BUFFER_RESULT)));
1657
uint32_t no_jbuf_after= make_join_orderinfo(this);
1658
uint64_t select_opts_for_readinfo=
1659
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
1661
sj_tmp_tables= NULL;
1662
if (!select_lex->sj_nests.is_empty())
1663
setup_semijoin_dups_elimination(this, select_opts_for_readinfo,
1666
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1667
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1670
/* Create all structures needed for materialized subquery execution. */
1671
if (setup_subquery_materialization())
1675
is this simple IN subquery?
1677
if (!group_list && !order &&
1678
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1679
tables == 1 && conds &&
1685
if (join_tab[0].type == JT_EQ_REF &&
1686
join_tab[0].ref.items[0]->name == in_left_expr_name)
1688
remove_subq_pushed_predicates(&where);
1689
save_index_subquery_explain_info(join_tab, where);
1690
join_tab[0].type= JT_UNIQUE_SUBQUERY;
1694
subselect_uniquesubquery_engine(session,
1699
else if (join_tab[0].type == JT_REF &&
1700
join_tab[0].ref.items[0]->name == in_left_expr_name)
1702
remove_subq_pushed_predicates(&where);
1703
save_index_subquery_explain_info(join_tab, where);
1704
join_tab[0].type= JT_INDEX_SUBQUERY;
1708
subselect_indexsubquery_engine(session,
1715
} else if (join_tab[0].type == JT_REF_OR_NULL &&
1716
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1717
having->name == in_having_cond)
1719
join_tab[0].type= JT_INDEX_SUBQUERY;
1721
conds= remove_additional_cond(conds);
1722
save_index_subquery_explain_info(join_tab, conds);
1724
change_engine(new subselect_indexsubquery_engine(session,
1734
Need to tell handlers that to play it safe, it should fetch all
1735
columns of the primary key of the tables: this is because MySQL may
1736
build row pointers for the rows, and for all columns of the primary key
1737
the read set has not necessarily been set by the server code.
1739
if (need_tmp || select_distinct || group_list || order)
1741
for (uint32_t i = const_tables; i < tables; i++)
1742
join_tab[i].table->prepare_for_position();
1745
if (const_tables != tables)
1748
Because filesort always does a full table scan or a quick range scan
1749
we must add the removed reference to the select for the table.
1750
We only need to do this when we have a simple_order or simple_group
1751
as in other cases the join is done before the sort.
1753
if ((order || group_list) &&
1754
(join_tab[const_tables].type != JT_ALL) &&
1755
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
1756
((order && simple_order) || (group_list && simple_group)))
1758
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
1763
if (!(select_options & SELECT_BIG_RESULT) &&
1766
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1767
unit->select_limit_cnt, 0,
1768
&join_tab[const_tables].table->
1769
keys_in_use_for_group_by))) ||
1771
tmp_table_param.quick_group)
1773
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1778
Force using of tmp table if sorting by a SP or UDF function due to
1779
their expensive and probably non-deterministic nature.
1781
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1783
Item *item= *tmp_order->item;
1784
if (item->is_expensive())
1786
/* Force tmp table without sort */
1787
need_tmp=1; simple_order=simple_group=0;
1795
if (select_options & SELECT_DESCRIBE)
1803
The loose index scan access method guarantees that all grouping or
1804
duplicate row elimination (for distinct) is already performed
1805
during data retrieval, and that all MIN/MAX functions are already
1806
computed for each group. Thus all MIN/MAX functions should be
1807
treated as regular functions, and there is no need to perform
1808
grouping in the main execution loop.
1809
Notice that currently loose index scan is applicable only for
1810
single table queries, thus it is sufficient to test only the first
1811
join_tab element of the plan for its access method.
1813
if (join_tab->is_using_loose_index_scan())
1814
tmp_table_param.precomputed_group_by= true;
1816
/* Create a tmp table if distinct or if the sort is too complicated */
1819
session->set_proc_info("Creating tmp table");
1821
init_items_ref_array();
1823
tmp_table_param.hidden_field_count= (all_fields.elements -
1824
fields_list.elements);
1825
order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1828
Pushing LIMIT to the temporary table creation is not applicable
1829
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1830
there are aggregate functions, because in all these cases we need
1833
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1835
!session->lex->current_select->with_sum_func) ?
1836
select_limit : HA_POS_ERROR;
1838
if (!(exec_tmp_table1=
1839
create_tmp_table(session, &tmp_table_param, all_fields,
1841
group_list ? 0 : select_distinct,
1842
group_list && simple_group,
1851
We don't have to store rows in temp table that doesn't match HAVING if:
1852
- we are sorting the table and writing complete group rows to the
1854
- We are using DISTINCT without resolving the distinct as a GROUP BY
1857
If having is not handled here, it will be checked before the row
1858
is sent to the client.
1861
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1864
/* if group or order on first table, sort first */
1865
if (group_list && simple_group)
1867
session->set_proc_info("Sorting for group");
1868
if (create_sort_index(session, this, group_list,
1869
HA_POS_ERROR, HA_POS_ERROR, false) ||
1870
alloc_group_fields(this, group_list) ||
1871
make_sum_func_list(all_fields, fields_list, 1) ||
1872
setup_sum_funcs(session, sum_funcs))
1880
if (make_sum_func_list(all_fields, fields_list, 0) ||
1881
setup_sum_funcs(session, sum_funcs))
1886
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1888
session->set_proc_info("Sorting for order");
1889
if (create_sort_index(session, this, order,
1890
HA_POS_ERROR, HA_POS_ERROR, true))
1899
Optimize distinct when used on some of the tables
1900
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1901
In this case we can stop scanning t2 when we have found one t1.a
1904
if (exec_tmp_table1->distinct)
1906
table_map used_tables= session->used_tables;
1907
JOIN_TAB *last_join_tab= join_tab+tables-1;
1910
if (used_tables & last_join_tab->table->map)
1912
last_join_tab->not_used_in_distinct=1;
1913
} while (last_join_tab-- != join_tab);
1914
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1915
if (order && skip_sort_order)
1917
/* Should always succeed */
1918
if (test_if_skip_sort_order(&join_tab[const_tables],
1919
order, unit->select_limit_cnt, 0,
1920
&join_tab[const_tables].table->
1921
keys_in_use_for_order_by))
1927
If this join belongs to an uncacheable subquery save
1930
if (select_lex->uncacheable && !is_top_level_join() &&
1931
init_save_join_tab())
1932
return(-1); /* purecov: inspected */
1941
Restore values in temporary join.
1943
void JOIN::restore_tmp()
1945
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1952
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1953
select_lex->offset_limit->val_uint() :
1958
if (exec_tmp_table1)
1960
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1961
exec_tmp_table1->file->ha_delete_all_rows();
1962
free_io_cache(exec_tmp_table1);
1963
filesort_free_buffers(exec_tmp_table1,0);
1965
if (exec_tmp_table2)
1967
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1968
exec_tmp_table2->file->ha_delete_all_rows();
1969
free_io_cache(exec_tmp_table2);
1970
filesort_free_buffers(exec_tmp_table2,0);
1973
set_items_ref_array(items0);
1976
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1981
/* Reset of sum functions */
1984
Item_sum *func, **func_ptr= sum_funcs;
1985
while ((func= *(func_ptr++)))
1993
@brief Save the original join layout
1995
@details Saves the original join layout so it can be reused in
1996
re-execution and for EXPLAIN.
1998
@return Operation status
2000
@retval 1 error occurred.
2004
JOIN::init_save_join_tab()
2006
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
2007
return 1; /* purecov: inspected */
2008
error= 0; // Ensure that tmp_join.error= 0
2015
JOIN::save_join_tab()
2017
if (!join_tab_save && select_lex->master_unit()->uncacheable)
2019
if (!(join_tab_save= (JOIN_TAB*)session->memdup((unsigned char*) join_tab,
2020
sizeof(JOIN_TAB) * tables)))
2031
Note, that create_sort_index calls test_if_skip_sort_order and may
2032
finally replace sorting with index scan if there is a LIMIT clause in
2033
the query. It's never shown in EXPLAIN!
2036
When can we have here session->net.report_error not zero?
2041
List<Item> *columns_list= &fields_list;
2044
session->set_proc_info("executing");
2046
(void) result->prepare2(); // Currently, this cannot fail.
2048
if (!tables_list && (tables || !select_lex->with_sum_func))
2049
{ // Only test of functions
2050
if (select_options & SELECT_DESCRIBE)
2051
select_describe(this, false, false, false,
2052
(zero_result_cause?zero_result_cause:"No tables used"));
2055
result->send_fields(*columns_list,
2056
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2058
We have to test for 'conds' here as the WHERE may not be constant
2059
even if we don't have any tables for prepared statements or if
2060
conds uses something like 'rand()'.
2062
if (cond_value != Item::COND_FALSE &&
2063
(!conds || conds->val_int()) &&
2064
(!having || having->val_int()))
2066
if (do_send_rows && result->send_data(fields_list))
2070
error= (int) result->send_eof();
2071
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 :
2072
session->sent_row_count);
2077
error=(int) result->send_eof();
2081
/* Single select (without union) always returns 0 or 1 row */
2082
session->limit_found_rows= send_records;
2083
session->examined_row_count= 0;
2087
Don't reset the found rows count if there're no tables as
2088
FOUND_ROWS() may be called. Never reset the examined row count here.
2089
It must be accumulated from all join iterations of all join parts.
2092
session->limit_found_rows= 0;
2094
if (zero_result_cause)
2096
(void) return_zero_rows(this, result, select_lex->leaf_tables,
2098
send_row_on_empty_set(),
2105
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) &&
2106
get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
2109
if (select_options & SELECT_DESCRIBE)
2112
Check if we managed to optimize order_st BY away and don't use temporary
2113
table to resolve order_st BY: in that case, we only may need to do
2114
filesort for GROUP BY.
2116
if (!order && !no_order && (!skip_sort_order || !need_tmp))
2119
Reset 'order' to 'group_list' and reinit variables describing
2123
simple_order= simple_group;
2127
(order != group_list || !(select_options & SELECT_BIG_RESULT)) &&
2128
(const_tables == tables ||
2129
((simple_order || skip_sort_order) &&
2130
test_if_skip_sort_order(&join_tab[const_tables], order,
2132
&join_tab[const_tables].table->
2133
keys_in_use_for_query))))
2136
select_describe(this, need_tmp,
2137
order != 0 && !skip_sort_order,
2139
!tables ? "No tables used" : NULL);
2143
JOIN *curr_join= this;
2144
List<Item> *curr_all_fields= &all_fields;
2145
List<Item> *curr_fields_list= &fields_list;
2146
Table *curr_tmp_table= 0;
2148
Initialize examined rows here because the values from all join parts
2149
must be accumulated in examined_row_count. Hence every join
2150
iteration must count from zero.
2152
curr_join->examined_rows= 0;
2154
/* Create a tmp table if distinct or if the sort is too complicated */
2160
We are in a non cacheable sub query. Get the saved join structure
2162
(curr_join may have been modified during last exection and we need
2165
curr_join= tmp_join;
2167
curr_tmp_table= exec_tmp_table1;
2169
/* Copy data to the temporary table */
2170
session->set_proc_info("Copying to tmp table");
2171
if (!curr_join->sort_and_group &&
2172
curr_join->const_tables != curr_join->tables)
2173
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2174
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2179
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
2181
if (curr_join->having)
2182
curr_join->having= curr_join->tmp_having= 0; // Allready done
2184
/* Change sum_fields reference to calculated fields in tmp_table */
2185
curr_join->all_fields= *curr_all_fields;
2188
items1= items0 + all_fields.elements;
2189
if (sort_and_group || curr_tmp_table->group)
2191
if (change_to_use_tmp_fields(session, items1,
2192
tmp_fields_list1, tmp_all_fields1,
2193
fields_list.elements, all_fields))
2198
if (change_refs_to_tmp_fields(session, items1,
2199
tmp_fields_list1, tmp_all_fields1,
2200
fields_list.elements, all_fields))
2203
curr_join->tmp_all_fields1= tmp_all_fields1;
2204
curr_join->tmp_fields_list1= tmp_fields_list1;
2205
curr_join->items1= items1;
2207
curr_all_fields= &tmp_all_fields1;
2208
curr_fields_list= &tmp_fields_list1;
2209
curr_join->set_items_ref_array(items1);
2211
if (sort_and_group || curr_tmp_table->group)
2213
curr_join->tmp_table_param.field_count+=
2214
curr_join->tmp_table_param.sum_func_count+
2215
curr_join->tmp_table_param.func_count;
2216
curr_join->tmp_table_param.sum_func_count=
2217
curr_join->tmp_table_param.func_count= 0;
2221
curr_join->tmp_table_param.field_count+=
2222
curr_join->tmp_table_param.func_count;
2223
curr_join->tmp_table_param.func_count= 0;
2226
if (curr_tmp_table->group)
2227
{ // Already grouped
2228
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
2229
curr_join->order= curr_join->group_list; /* order by group */
2230
curr_join->group_list= 0;
2234
If we have different sort & group then we must sort the data by group
2235
and copy it to another tmp table
2236
This code is also used if we are using distinct something
2237
we haven't been able to store in the temporary table yet
2238
like SEC_TO_TIME(SUM(...)).
2241
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))
2242
{ /* Must copy to another table */
2243
/* Free first data from old join */
2244
curr_join->join_free();
2245
if (make_simple_join(curr_join, curr_tmp_table))
2247
calc_group_buffer(curr_join, group_list);
2248
count_field_types(select_lex, &curr_join->tmp_table_param,
2249
curr_join->tmp_all_fields1,
2250
curr_join->select_distinct && !curr_join->group_list);
2251
curr_join->tmp_table_param.hidden_field_count=
2252
(curr_join->tmp_all_fields1.elements-
2253
curr_join->tmp_fields_list1.elements);
2256
if (exec_tmp_table2)
2257
curr_tmp_table= exec_tmp_table2;
2260
/* group data to new table */
2263
If the access method is loose index scan then all MIN/MAX
2264
functions are precomputed, and should be treated as regular
2265
functions. See extended comment in JOIN::exec.
2267
if (curr_join->join_tab->is_using_loose_index_scan())
2268
curr_join->tmp_table_param.precomputed_group_by= true;
2270
if (!(curr_tmp_table=
2271
exec_tmp_table2= create_tmp_table(session,
2272
&curr_join->tmp_table_param,
2275
curr_join->select_distinct &&
2276
!curr_join->group_list,
2277
1, curr_join->select_options,
2281
curr_join->exec_tmp_table2= exec_tmp_table2;
2283
if (curr_join->group_list)
2285
session->set_proc_info("Creating sort index");
2286
if (curr_join->join_tab == join_tab && save_join_tab())
2290
if (create_sort_index(session, curr_join, curr_join->group_list,
2291
HA_POS_ERROR, HA_POS_ERROR, false) ||
2292
make_group_fields(this, curr_join))
2296
sortorder= curr_join->sortorder;
2299
session->set_proc_info("Copying to group table");
2301
if (curr_join != this)
2305
curr_join->sum_funcs= sum_funcs2;
2306
curr_join->sum_funcs_end= sum_funcs_end2;
2310
curr_join->alloc_func_list();
2311
sum_funcs2= curr_join->sum_funcs;
2312
sum_funcs_end2= curr_join->sum_funcs_end;
2315
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2318
curr_join->group_list= 0;
2319
if (!curr_join->sort_and_group &&
2320
curr_join->const_tables != curr_join->tables)
2321
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2322
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2323
(tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2328
end_read_record(&curr_join->join_tab->read_record);
2329
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
2330
curr_join->join_tab[0].table= 0; // Table is freed
2332
// No sum funcs anymore
2335
items2= items1 + all_fields.elements;
2336
if (change_to_use_tmp_fields(session, items2,
2337
tmp_fields_list2, tmp_all_fields2,
2338
fields_list.elements, tmp_all_fields1))
2340
curr_join->tmp_fields_list2= tmp_fields_list2;
2341
curr_join->tmp_all_fields2= tmp_all_fields2;
2343
curr_fields_list= &curr_join->tmp_fields_list2;
2344
curr_all_fields= &curr_join->tmp_all_fields2;
2345
curr_join->set_items_ref_array(items2);
2346
curr_join->tmp_table_param.field_count+=
2347
curr_join->tmp_table_param.sum_func_count;
2348
curr_join->tmp_table_param.sum_func_count= 0;
2350
if (curr_tmp_table->distinct)
2351
curr_join->select_distinct=0; /* Each row is unique */
2353
curr_join->join_free(); /* Free quick selects */
2354
if (curr_join->select_distinct && ! curr_join->group_list)
2356
session->set_proc_info("Removing duplicates");
2357
if (curr_join->tmp_having)
2358
curr_join->tmp_having->update_used_tables();
2359
if (remove_duplicates(curr_join, curr_tmp_table,
2360
*curr_fields_list, curr_join->tmp_having))
2362
curr_join->tmp_having=0;
2363
curr_join->select_distinct=0;
2365
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
2366
if (make_simple_join(curr_join, curr_tmp_table))
2368
calc_group_buffer(curr_join, curr_join->group_list);
2369
count_field_types(select_lex, &curr_join->tmp_table_param,
2370
*curr_all_fields, 0);
2374
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
2376
if (make_group_fields(this, curr_join))
2383
init_items_ref_array();
2384
items3= ref_pointer_array + (all_fields.elements*4);
2385
setup_copy_fields(session, &curr_join->tmp_table_param,
2386
items3, tmp_fields_list3, tmp_all_fields3,
2387
curr_fields_list->elements, *curr_all_fields);
2388
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
2389
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
2390
tmp_table_param.save_copy_field_end=
2391
curr_join->tmp_table_param.copy_field_end;
2392
curr_join->tmp_all_fields3= tmp_all_fields3;
2393
curr_join->tmp_fields_list3= tmp_fields_list3;
2397
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
2398
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
2399
curr_join->tmp_table_param.copy_field_end=
2400
tmp_table_param.save_copy_field_end;
2402
curr_fields_list= &tmp_fields_list3;
2403
curr_all_fields= &tmp_all_fields3;
2404
curr_join->set_items_ref_array(items3);
2406
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2408
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2409
session->is_fatal_error)
2412
if (curr_join->group_list || curr_join->order)
2414
session->set_proc_info("Sorting result");
2415
/* If we have already done the group, add HAVING to sorted table */
2416
if (curr_join->tmp_having && ! curr_join->group_list &&
2417
! curr_join->sort_and_group)
2419
// Some tables may have been const
2420
curr_join->tmp_having->update_used_tables();
2421
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
2422
table_map used_tables= (curr_join->const_table_map |
2423
curr_table->table->map);
2425
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having,
2428
if (sort_table_cond)
2430
if (!curr_table->select)
2431
if (!(curr_table->select= new SQL_SELECT))
2433
if (!curr_table->select->cond)
2434
curr_table->select->cond= sort_table_cond;
2435
else // This should never happen
2437
if (!(curr_table->select->cond=
2438
new Item_cond_and(curr_table->select->cond,
2442
Item_cond_and do not need fix_fields for execution, its parameters
2443
are fixed or do not need fix_fields, too
2445
curr_table->select->cond->quick_fix_field();
2447
curr_table->select_cond= curr_table->select->cond;
2448
curr_table->select_cond->top_level_item();
2449
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
2456
curr_join->select_limit= HA_POS_ERROR;
2460
We can abort sorting after session->select_limit rows if we there is no
2461
WHERE clause for any tables after the sorted one.
2463
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
2464
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
2465
for (; curr_table < end_table ; curr_table++)
2468
table->keyuse is set in the case there was an original WHERE clause
2469
on the table that was optimized away.
2471
if (curr_table->select_cond ||
2472
(curr_table->keyuse && !curr_table->first_inner))
2474
/* We have to sort all rows */
2475
curr_join->select_limit= HA_POS_ERROR;
2480
if (curr_join->join_tab == join_tab && save_join_tab())
2485
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
2486
chose FILESORT to be faster than INDEX SCAN or there is no
2487
suitable index present.
2488
Note, that create_sort_index calls test_if_skip_sort_order and may
2489
finally replace sorting with index scan if there is a LIMIT clause in
2490
the query. XXX: it's never shown in EXPLAIN!
2491
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
2493
if (create_sort_index(session, curr_join,
2494
curr_join->group_list ?
2495
curr_join->group_list : curr_join->order,
2496
curr_join->select_limit,
2497
(select_options & OPTION_FOUND_ROWS ?
2498
HA_POS_ERROR : unit->select_limit_cnt),
2499
curr_join->group_list ? true : false))
2501
sortorder= curr_join->sortorder;
2502
if (curr_join->const_tables != curr_join->tables &&
2503
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
2506
If no IO cache exists for the first table then we are using an
2507
INDEX SCAN and no filesort. Thus we should not remove the sorted
2508
attribute on the INDEX SCAN.
2514
/* XXX: When can we have here session->is_error() not zero? */
2515
if (session->is_error())
2517
error= session->is_error();
2520
curr_join->having= curr_join->tmp_having;
2521
curr_join->fields= curr_fields_list;
2524
session->set_proc_info("Sending data");
2525
result->send_fields(*curr_fields_list,
2526
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2527
error= do_select(curr_join, curr_fields_list, NULL);
2528
session->limit_found_rows= curr_join->send_records;
2531
/* Accumulate the counts from all join iterations of all join parts. */
2532
session->examined_row_count+= curr_join->examined_rows;
2535
With EXPLAIN EXTENDED we have to restore original ref_array
2536
for a derived table which is always materialized.
2537
Otherwise we would not be able to print the query correctly.
2540
(session->lex->describe & DESCRIBE_EXTENDED) &&
2541
select_lex->linkage == DERIVED_TABLE_TYPE)
2542
set_items_ref_array(items0);
2552
Return error that hold JOIN.
2558
select_lex->join= 0;
2562
if (join_tab != tmp_join->join_tab)
2564
JOIN_TAB *tab, *end;
2565
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
2568
tmp_join->tmp_join= 0;
2569
tmp_table_param.copy_field=0;
2570
return(tmp_join->destroy());
2575
if (exec_tmp_table1)
2576
exec_tmp_table1->free_tmp_table(session);
2577
if (exec_tmp_table2)
2578
exec_tmp_table2->free_tmp_table(session);
2580
delete_dynamic(&keyuse);
2587
327
An entry point to single-unit select (a select without UNION).
2589
@param session thread handler
329
@param session thread Cursor
2590
330
@param rref_pointer_array a reference to ref_pointer_array of
2591
331
the top-level select_lex for this query
2592
332
@param tables list of all tables used in this query.
2723
461
return(join->error);
2727
int subq_sj_candidate_cmp(Item_in_subselect* const *el1,
2728
Item_in_subselect* const *el2)
2730
return ((*el1)->sj_convert_priority < (*el2)->sj_convert_priority) ? 1 :
2731
( ((*el1)->sj_convert_priority == (*el2)->sj_convert_priority)? 0 : -1);
2735
inline Item * and_items(Item* cond, Item *item)
464
inline Item *and_items(Item* cond, Item *item)
2737
466
return (cond? (new Item_cond_and(cond, item)) : item);
2741
static TableList *alloc_join_nest(Session *session)
2744
if (!(tbl= (TableList*) session->calloc(ALIGN_SIZE(sizeof(TableList))+
2745
sizeof(nested_join_st))))
2747
tbl->nested_join= (nested_join_st*) ((unsigned char*)tbl +
2748
ALIGN_SIZE(sizeof(TableList)));
2753
void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TableList> *tlist)
2755
List_iterator<TableList> it(*tlist);
2757
while ((table= it++))
2760
table->on_expr->fix_after_pullout(new_parent, &table->on_expr);
2761
if (table->nested_join)
2762
fix_list_after_tbl_changes(new_parent, &table->nested_join->join_list);
2768
Convert a subquery predicate into a TableList semi-join nest
2771
convert_subq_to_sj()
2772
parent_join Parent join, the one that has subq_pred in its WHERE/ON
2774
subq_pred Subquery predicate to be converted
2777
Convert a subquery predicate into a TableList semi-join nest. All the
2778
prerequisites are already checked, so the conversion is always successfull.
2780
Prepared Statements: the transformation is permanent:
2781
- Changes in TableList structures are naturally permanent
2782
- Item tree changes are performed on statement MEM_ROOT:
2783
= we activate statement MEM_ROOT
2784
= this function is called before the first fix_prepare_information
2787
This is intended because the criteria for subquery-to-sj conversion remain
2788
constant for the lifetime of the Prepared Statement.
2792
true Out of memory error
2795
bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
2797
SELECT_LEX *parent_lex= parent_join->select_lex;
2798
TableList *emb_tbl_nest= NULL;
2799
List<TableList> *emb_join_list= &parent_lex->top_join_list;
2800
Session *session= parent_join->session;
2803
1. Find out where to put the predicate into.
2804
Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
2806
if ((void*)subq_pred->expr_join_nest != (void*)1)
2808
if (subq_pred->expr_join_nest->nested_join)
2813
... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
2815
The sj-nest will be inserted into the brackets nest.
2817
emb_tbl_nest= subq_pred->expr_join_nest;
2818
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2820
else if (!subq_pred->expr_join_nest->outer_join)
2825
... INNER JOIN tblX ON (subquery AND whatever) ...
2827
The sj-nest will be tblX's "sibling", i.e. another child of its
2828
parent. This is ok because tblX is joined as an inner join.
2830
emb_tbl_nest= subq_pred->expr_join_nest->embedding;
2832
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2834
else if (!subq_pred->expr_join_nest->nested_join)
2836
TableList *outer_tbl= subq_pred->expr_join_nest;
2837
TableList *wrap_nest;
2841
... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
2843
we'll need to convert it into:
2845
... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
2847
|<----- wrap_nest ---->|
2849
Q: other subqueries may be pointing to this element. What to do?
2850
A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
2851
But we'll need to fix other pointers.
2852
A2: Another way: have TableList::next_ptr so the following
2853
subqueries know the table has been nested.
2854
A3: changes in the TableList::outer_join will make everything work
2857
if (!(wrap_nest= alloc_join_nest(parent_join->session)))
2861
wrap_nest->embedding= outer_tbl->embedding;
2862
wrap_nest->join_list= outer_tbl->join_list;
2863
wrap_nest->alias= (char*) "(sj-wrap)";
2865
wrap_nest->nested_join->join_list.empty();
2866
wrap_nest->nested_join->join_list.push_back(outer_tbl);
2868
outer_tbl->embedding= wrap_nest;
2869
outer_tbl->join_list= &wrap_nest->nested_join->join_list;
2872
wrap_nest will take place of outer_tbl, so move the outer join flag
2875
wrap_nest->outer_join= outer_tbl->outer_join;
2876
outer_tbl->outer_join= 0;
2878
wrap_nest->on_expr= outer_tbl->on_expr;
2879
outer_tbl->on_expr= NULL;
2881
List_iterator<TableList> li(*wrap_nest->join_list);
2885
if (tbl == outer_tbl)
2887
li.replace(wrap_nest);
2892
Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
2893
semi-join nest into it
2895
emb_join_list= &wrap_nest->nested_join->join_list;
2896
emb_tbl_nest= wrap_nest;
2901
nested_join_st *nested_join;
2902
if (!(sj_nest= alloc_join_nest(parent_join->session)))
2906
nested_join= sj_nest->nested_join;
2908
sj_nest->join_list= emb_join_list;
2909
sj_nest->embedding= emb_tbl_nest;
2910
sj_nest->alias= (char*) "(sj-nest)";
2911
/* Nests do not participate in those 'chains', so: */
2912
/* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
2913
emb_join_list->push_back(sj_nest);
2916
nested_join->used_tables and nested_join->not_null_tables are
2917
initialized in simplify_joins().
2921
2. Walk through subquery's top list and set 'embedding' to point to the
2924
st_select_lex *subq_lex= subq_pred->unit->first_select();
2925
nested_join->join_list.empty();
2926
List_iterator_fast<TableList> li(subq_lex->top_join_list);
2927
TableList *tl, *last_leaf;
2930
tl->embedding= sj_nest;
2931
tl->join_list= &nested_join->join_list;
2932
nested_join->join_list.push_back(tl);
2936
Reconnect the next_leaf chain.
2937
TODO: Do we have to put subquery's tables at the end of the chain?
2938
Inserting them at the beginning would be a bit faster.
2939
NOTE: We actually insert them at the front! That's because the order is
2940
reversed in this list.
2942
for (tl= parent_lex->leaf_tables; tl->next_leaf; tl= tl->next_leaf) {};
2943
tl->next_leaf= subq_lex->leaf_tables;
2947
Same as above for next_local chain
2948
(a theory: a next_local chain always starts with ::leaf_tables
2949
because view's tables are inserted after the view)
2951
for (tl= parent_lex->leaf_tables; tl->next_local; tl= tl->next_local) {};
2952
tl->next_local= subq_lex->leaf_tables;
2954
/* A theory: no need to re-connect the next_global chain */
2956
/* 3. Remove the original subquery predicate from the WHERE/ON */
2958
// The subqueries were replaced for Item_int(1) earlier
2959
subq_pred->exec_method= Item_in_subselect::SEMI_JOIN; // for subsequent executions
2960
/*TODO: also reset the 'with_subselect' there. */
2962
/* n. Adjust the parent_join->tables counter */
2963
uint32_t table_no= parent_join->tables;
2964
/* n. Walk through child's tables and adjust table->map */
2965
for (tl= subq_lex->leaf_tables; tl; tl= tl->next_leaf, table_no++)
2967
tl->table->tablenr= table_no;
2968
tl->table->map= ((table_map)1) << table_no;
2969
SELECT_LEX *old_sl= tl->select_lex;
2970
tl->select_lex= parent_join->select_lex;
2971
for(TableList *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)
2972
emb->select_lex= parent_join->select_lex;
2974
parent_join->tables += subq_lex->join->tables;
2977
Put the subquery's WHERE into semi-join's sj_on_expr
2978
Add the subquery-induced equalities too.
2980
SELECT_LEX *save_lex= session->lex->current_select;
2981
session->lex->current_select=subq_lex;
2982
if (!subq_pred->left_expr->fixed &&
2983
subq_pred->left_expr->fix_fields(session, &subq_pred->left_expr))
2985
session->lex->current_select=save_lex;
2987
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
2988
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables() |
2989
subq_pred->left_expr->used_tables();
2990
sj_nest->sj_on_expr= subq_lex->where;
2993
Create the IN-equalities and inject them into semi-join's ON expression.
2994
Additionally, for InsideOut strategy
2995
- Record the number of IN-equalities.
2996
- Create list of pointers to (oe1, ..., ieN). We'll need the list to
2997
see which of the expressions are bound and which are not (for those
2998
we'll produce a distinct stream of (ie_i1,...ie_ik).
3000
(TODO: can we just create a list of pointers and hope the expressions
3001
will not substitute themselves on fix_fields()? or we need to wrap
3002
them into Item_direct_view_refs and store pointers to those. The
3003
pointers to Item_direct_view_refs are guaranteed to be stable as
3004
Item_direct_view_refs doesn't substitute itself with anything in
3005
Item_direct_view_ref::fix_fields.
3007
sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
3008
sj_nest->nested_join->sj_outer_expr_list.empty();
3010
if (subq_pred->left_expr->cols() == 1)
3012
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr);
3014
Item *item_eq= new Item_func_eq(subq_pred->left_expr,
3015
subq_lex->ref_pointer_array[0]);
3016
item_eq->name= (char*)subq_sj_cond_name;
3017
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3021
for (uint32_t i= 0; i < subq_pred->left_expr->cols(); i++)
3023
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->
3026
new Item_func_eq(subq_pred->left_expr->element_index(i),
3027
subq_lex->ref_pointer_array[i]);
3028
item_eq->name= (char*)subq_sj_cond_name + (i % 64);
3029
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3032
/* Fix the created equality and AND */
3033
sj_nest->sj_on_expr->fix_fields(parent_join->session, &sj_nest->sj_on_expr);
3036
Walk through sj nest's WHERE and ON expressions and call
3037
item->fix_table_changes() for all items.
3039
sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr);
3040
fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
3043
/* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
3044
subq_lex->master_unit()->exclude_level();
3046
/* Inject sj_on_expr into the parent's WHERE or ON */
3049
emb_tbl_nest->on_expr= and_items(emb_tbl_nest->on_expr,
3050
sj_nest->sj_on_expr);
3051
emb_tbl_nest->on_expr->fix_fields(parent_join->session, &emb_tbl_nest->on_expr);
3055
/* Inject into the WHERE */
3056
parent_join->conds= and_items(parent_join->conds, sj_nest->sj_on_expr);
3057
parent_join->conds->fix_fields(parent_join->session, &parent_join->conds);
3058
parent_join->select_lex->where= parent_join->conds;
3066
Convert candidate subquery predicates to semi-joins
3069
JOIN::flatten_subqueries()
3072
Convert candidate subquery predicates to semi-joins.
3079
bool JOIN::flatten_subqueries()
3081
Item_in_subselect **in_subq;
3082
Item_in_subselect **in_subq_end;
3084
if (sj_subselects.elements() == 0)
3087
/* 1. Fix children subqueries */
3088
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
3089
in_subq != in_subq_end; in_subq++)
3091
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3092
child_join->outer_tables = child_join->tables;
3093
if (child_join->flatten_subqueries())
3095
(*in_subq)->sj_convert_priority=
3096
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
3100
2. Pick which subqueries to convert:
3101
sort the subquery array
3102
- prefer correlated subqueries over uncorrelated;
3103
- prefer subqueries that have greater number of outer tables;
3105
sj_subselects.sort(subq_sj_candidate_cmp);
3106
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
3107
/* Replace all subqueries to be flattened with Item_int(1) */
3108
for (in_subq= sj_subselects.front();
3109
in_subq != in_subq_end &&
3110
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3113
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
3117
for (in_subq= sj_subselects.front();
3118
in_subq != in_subq_end &&
3119
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3122
if (convert_subq_to_sj(this, *in_subq))
3126
/* 3. Finalize those we didn't convert */
3127
for (; in_subq!= in_subq_end; in_subq++)
3129
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3130
Item_subselect::trans_res res;
3131
(*in_subq)->changed= 0;
3132
(*in_subq)->fixed= 0;
3133
res= (*in_subq)->select_transformer(child_join);
3134
if (res == Item_subselect::RES_ERROR)
3137
(*in_subq)->changed= 1;
3138
(*in_subq)->fixed= 1;
3140
Item *substitute= (*in_subq)->substitution;
3141
bool do_fix_fields= !(*in_subq)->substitution->fixed;
3142
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
3145
//if ((*in_subq)->fix_fields(session, (*in_subq)->ref_ptr))
3148
sj_subselects.clear();
3154
Setup for execution all subqueries of a query, for which the optimizer
3155
chose hash semi-join.
3157
@details Iterate over all subqueries of the query, and if they are under an
3158
IN predicate, and the optimizer chose to compute it via hash semi-join:
3159
- try to initialize all data structures needed for the materialized execution
3160
of the IN predicate,
3161
- if this fails, then perform the IN=>EXISTS transformation which was
3162
previously blocked during JOIN::prepare.
3164
This method is part of the "code generation" query processing phase.
3166
This phase must be called after substitute_for_best_equal_field() because
3167
that function may replace items with other items from a multiple equality,
3168
and we need to reference the correct items in the index access method of the
3171
@return Operation status
3172
@retval false success.
3173
@retval true error occurred.
3176
bool JOIN::setup_subquery_materialization()
3178
for (SELECT_LEX_UNIT *un= select_lex->first_inner_unit(); un;
3179
un= un->next_unit())
3181
for (SELECT_LEX *sl= un->first_select(); sl; sl= sl->next_select())
3183
Item_subselect *subquery_predicate= sl->master_unit()->item;
3184
if (subquery_predicate &&
3185
subquery_predicate->substype() == Item_subselect::IN_SUBS)
3187
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
3188
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
3189
in_subs->setup_engine())
3199
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3202
find_eq_ref_candidate()
3203
table Table to be checked
3204
sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
3208
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3211
Check again if it is feasible to factor common parts with constant table
3215
true - There exists an eq_ref(outer-tables) candidate
3219
bool find_eq_ref_candidate(Table *table, table_map sj_inner_tables)
3221
KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
3226
while (1) /* For each key */
3229
KEY *keyinfo= table->key_info + key;
3230
key_part_map bound_parts= 0;
3231
if ((keyinfo->flags & HA_NOSAME) == HA_NOSAME)
3233
do /* For all equalities on all key parts */
3235
/* Check if this is "t.keypart = expr(outer_tables) */
3236
if (!(keyuse->used_tables & sj_inner_tables) &&
3237
!(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
3239
bound_parts |= 1 << keyuse->keypart;
3242
} while (keyuse->key == key && keyuse->table == table);
3244
if (bound_parts == PREV_BITS(uint, keyinfo->key_parts))
3246
if (keyuse->table != table)
3254
if (keyuse->table != table)
3257
while (keyuse->key == key);
3266
Pull tables out of semi-join nests, if possible
3269
pull_out_semijoin_tables()
3270
join The join where to do the semi-join flattening
3273
Try to pull tables out of semi-join nests.
3276
When this function is called, the join may have several semi-join nests
3277
(possibly within different semi-join nests), but it is guaranteed that
3278
one semi-join nest does not contain another.
3281
A table can be pulled out of the semi-join nest if
3282
- It is a constant table
3286
* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer
3288
* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.
3289
* Semi-join nests TableList::sj_inner_tables
3291
This operation is (and should be) performed at each PS execution since
3292
tables may become/cease to be constant across PS reexecutions.
3296
1 - Out of memory error
3299
int pull_out_semijoin_tables(JOIN *join)
3302
List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);
3304
/* Try pulling out of the each of the semi-joins */
3305
while ((sj_nest= sj_list_it++))
3307
/* Action #1: Mark the constant tables to be pulled out */
3308
table_map pulled_tables= 0;
3310
List_iterator<TableList> child_li(sj_nest->nested_join->join_list);
3312
while ((tbl= child_li++))
3316
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
3317
if (tbl->table->map & join->const_table_map)
3319
pulled_tables |= tbl->table->map;
3325
Action #2: Find which tables we can pull out based on
3326
update_ref_and_keys() data. Note that pulling one table out can allow
3327
us to pull out some other tables too.
3329
bool pulled_a_table;
3332
pulled_a_table= false;
3334
while ((tbl= child_li++))
3336
if (tbl->table && !(pulled_tables & tbl->table->map))
3338
if (find_eq_ref_candidate(tbl->table,
3339
sj_nest->nested_join->used_tables &
3342
pulled_a_table= true;
3343
pulled_tables |= tbl->table->map;
3347
} while (pulled_a_table);
3350
if ((sj_nest)->nested_join->used_tables == pulled_tables)
3352
(sj_nest)->sj_inner_tables= 0;
3353
while ((tbl= child_li++))
3356
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3361
/* Record the bitmap of inner tables, mark the inner tables */
3362
table_map inner_tables=(sj_nest)->nested_join->used_tables &
3364
(sj_nest)->sj_inner_tables= inner_tables;
3365
while ((tbl= child_li++))
3369
if (inner_tables & tbl->table->map)
3370
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
3372
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3380
469
/*****************************************************************************
3381
Create JOIN_TABS, make a guess about the table types,
470
Create JoinTableS, make a guess about the table types,
3382
471
Approximate how many records will be used in each table
3383
472
*****************************************************************************/
3386
static ha_rows get_quick_record_count(Session *session, SQL_SELECT *select,
3388
const key_map *keys,ha_rows limit)
473
ha_rows get_quick_record_count(Session *session, optimizer::SqlSelect *select, Table *table, const key_map *keys,ha_rows limit)
3391
476
if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))
3392
return(0); // Fatal error flag is set
478
return 0; // Fatal error flag is set
3395
483
select->head=table;
3396
484
table->reginfo.impossible_range=0;
3397
485
if ((error= select->test_quick_select(session, *(key_map *)keys,(table_map) 0,
3398
486
limit, 0, false)) == 1)
3399
488
return(select->quick->records);
3400
491
if (error == -1)
3402
493
table->reginfo.impossible_range=1;
3406
498
return(HA_POS_ERROR); /* This shouldn't happend */
3410
This structure is used to collect info on potentially sargable
3411
predicates in order to check whether they become sargable after
3412
reading const tables.
3413
We form a bitmap of indexes that can be used for sargable predicates.
3414
Only such indexes are involved in range analysis.
3416
typedef struct st_sargable_param
3418
Field *field; /* field against which to check sargability */
3419
Item **arg_value; /* values of potential keys for lookups */
3420
uint32_t num_values; /* number of values in the above array */
3424
Calculate the best possible join and initialize the join structure.
3433
make_join_statistics(JOIN *join, TableList *tables, COND *conds,
3434
DYNAMIC_ARRAY *keyuse_array)
3438
uint32_t i,table_count,const_count,key;
3439
table_map found_const_table_map, all_table_map, found_ref, refs;
3440
key_map const_ref, eq_part;
3441
Table **table_vector;
3442
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
3443
KEYUSE *keyuse,*start_keyuse;
3444
table_map outer_join=0;
3445
SARGABLE_PARAM *sargables= 0;
3446
JOIN_TAB *stat_vector[MAX_TABLES+1];
3448
table_count=join->tables;
3449
stat=(JOIN_TAB*) join->session->calloc(sizeof(JOIN_TAB)*table_count);
3450
stat_ref=(JOIN_TAB**) join->session->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
3451
table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
3452
if (!stat || !stat_ref || !table_vector)
3453
return(1); // Eom /* purecov: inspected */
3455
join->best_ref=stat_vector;
3457
stat_end=stat+table_count;
3458
found_const_table_map= all_table_map=0;
3463
s++, tables= tables->next_leaf, i++)
3465
TableList *embedding= tables->embedding;
3468
s->const_keys.init();
3469
s->checked_keys.init();
3470
s->needed_reg.init();
3471
table_vector[i]=s->table=table=tables->table;
3472
table->pos_in_table_list= tables;
3473
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
3476
table->file->print_error(error, MYF(0));
3479
table->quick_keys.clear_all();
3480
table->reginfo.join_tab=s;
3481
table->reginfo.not_exists_optimize=0;
3482
memset(table->const_key_parts, 0,
3483
sizeof(key_part_map)*table->s->keys);
3484
all_table_map|= table->map;
3486
s->info=0; // For describe
3488
s->dependent= tables->dep_tables;
3489
s->key_dependent= 0;
3490
if (tables->schema_table)
3491
table->file->stats.records= 2;
3492
table->quick_condition_rows= table->file->stats.records;
3494
s->on_expr_ref= &tables->on_expr;
3495
if (*s->on_expr_ref)
3497
/* s is the only inner table of an outer join */
3498
if (!table->file->stats.records && !embedding)
3500
s->dependent= 0; // Ignore LEFT JOIN depend.
3501
set_position(join,const_count++,s,(KEYUSE*) 0);
3504
outer_join|= table->map;
3505
s->embedding_map= 0;
3506
for (;embedding; embedding= embedding->embedding)
3507
s->embedding_map|= embedding->nested_join->nj_map;
3510
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
3512
/* s belongs to a nested join, maybe to several embedded joins */
3513
s->embedding_map= 0;
3516
nested_join_st *nested_join= embedding->nested_join;
3517
s->embedding_map|=nested_join->nj_map;
3518
s->dependent|= embedding->dep_tables;
3519
embedding= embedding->embedding;
3520
outer_join|= nested_join->used_tables;
3525
if ((table->file->stats.records <= 1) &&
3527
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && !join->no_const_tables)
3529
set_position(join,const_count++,s,(KEYUSE*) 0);
3533
join->outer_join=outer_join;
3535
if (join->outer_join)
3538
Build transitive closure for relation 'to be dependent on'.
3539
This will speed up the plan search for many cases with outer joins,
3540
as well as allow us to catch illegal cross references/
3541
Warshall's algorithm is used to build the transitive closure.
3542
As we use bitmaps to represent the relation the complexity
3543
of the algorithm is O((number of tables)^2).
3545
for (i= 0, s= stat ; i < table_count ; i++, s++)
3547
for (uint32_t j= 0 ; j < table_count ; j++)
3549
table= stat[j].table;
3550
if (s->dependent & table->map)
3551
s->dependent |= table->reginfo.join_tab->dependent;
3554
s->table->maybe_null= 1;
3556
/* Catch illegal cross references for outer joins */
3557
for (i= 0, s= stat ; i < table_count ; i++, s++)
3559
if (s->dependent & s->table->map)
3561
join->tables=0; // Don't use join->table
3562
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
3565
s->key_dependent= s->dependent;
3569
if (conds || outer_join)
3570
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
3571
conds, join->cond_equal,
3572
~outer_join, join->select_lex, &sargables))
3575
/* Read tables with 0 or 1 rows (system tables) */
3576
join->const_table_map= 0;
3578
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
3585
join->const_table_map|=s->table->map;
3586
if ((tmp=join_read_const_table(s, p_pos)))
3589
return(1); // Fatal error
3592
found_const_table_map|= s->table->map;
3595
/* loop until no more const tables are found */
3599
more_const_tables_found:
3604
We only have to loop from stat_vector + const_count as
3605
set_position() will move all const_tables first in stat_vector
3608
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
3613
If equi-join condition by a key is null rejecting and after a
3614
substitution of a const table the key value happens to be null
3615
then we can state that there are no matches for this equi-join.
3617
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
3620
When performing an outer join operation if there are no matching rows
3621
for the single row of the outer table all the inner tables are to be
3622
null complemented and thus considered as constant tables.
3623
Here we apply this consideration to the case of outer join operations
3624
with a single inner table only because the case with nested tables
3625
would require a more thorough analysis.
3626
TODO. Apply single row substitution to null complemented inner tables
3627
for nested outer join operations.
3629
while (keyuse->table == table)
3631
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
3632
keyuse->val->is_null() && keyuse->null_rejecting)
3635
mark_as_null_row(table);
3636
found_const_table_map|= table->map;
3637
join->const_table_map|= table->map;
3638
set_position(join,const_count++,s,(KEYUSE*) 0);
3639
goto more_const_tables_found;
3645
if (s->dependent) // If dependent on some table
3647
// All dep. must be constants
3648
if (s->dependent & ~(found_const_table_map))
3650
if (table->file->stats.records <= 1L &&
3651
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
3652
!table->pos_in_table_list->embedding)
3656
join->const_table_map|=table->map;
3657
set_position(join,const_count++,s,(KEYUSE*) 0);
3658
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
3661
return(1); // Fatal error
3664
found_const_table_map|= table->map;
3668
/* check if table can be read by key or table only uses const refs */
3669
if ((keyuse=s->keyuse))
3672
while (keyuse->table == table)
3674
start_keyuse=keyuse;
3676
s->keys.set_bit(key); // QQ: remove this ?
3679
const_ref.clear_all();
3680
eq_part.clear_all();
3683
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
3685
if (!((~found_const_table_map) & keyuse->used_tables))
3686
const_ref.set_bit(keyuse->keypart);
3688
refs|=keyuse->used_tables;
3689
eq_part.set_bit(keyuse->keypart);
3692
} while (keyuse->table == table && keyuse->key == key);
3694
if (eq_part.is_prefix(table->key_info[key].key_parts) &&
3695
!table->pos_in_table_list->embedding)
3697
if ((table->key_info[key].flags & (HA_NOSAME))
3700
if (const_ref == eq_part)
3701
{ // Found everything for ref.
3705
join->const_table_map|=table->map;
3706
set_position(join,const_count++,s,start_keyuse);
3707
if (create_ref_for_key(join, s, start_keyuse,
3708
found_const_table_map))
3710
if ((tmp=join_read_const_table(s,
3711
join->positions+const_count-1)))
3714
return(1); // Fatal error
3717
found_const_table_map|= table->map;
3721
found_ref|= refs; // Table is const if all refs are const
3723
else if (const_ref == eq_part)
3724
s->const_keys.set_bit(key);
3729
} while (join->const_table_map & found_ref && ref_changed);
3732
Update info on indexes that can be used for search lookups as
3733
reading const tables may has added new sargable predicates.
3735
if (const_count && sargables)
3737
for( ; sargables->field ; sargables++)
3739
Field *field= sargables->field;
3740
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
3741
key_map possible_keys= field->key_start;
3742
possible_keys.intersect(field->table->keys_in_use_for_query);
3744
for (uint32_t j=0; j < sargables->num_values; j++)
3745
is_const&= sargables->arg_value[j]->const_item();
3747
join_tab[0].const_keys.merge(possible_keys);
3751
if (pull_out_semijoin_tables(join))
3754
/* Calc how many (possible) matched records in each table */
3756
for (s=stat ; s < stat_end ; s++)
3758
if (s->type == JT_SYSTEM || s->type == JT_CONST)
3760
/* Only one matching row */
3761
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
3764
/* Approximate found rows and time to read them */
3765
s->found_records=s->records=s->table->file->stats.records;
3766
s->read_time=(ha_rows) s->table->file->scan_time();
3769
Set a max range of how many seeks we can expect when using keys
3770
This is can't be to high as otherwise we are likely to use
3773
s->worst_seeks= cmin((double) s->found_records / 10,
3774
(double) s->read_time*3);
3775
if (s->worst_seeks < 2.0) // Fix for small tables
3779
Add to stat->const_keys those indexes for which all group fields or
3780
all select distinct fields participate in one index.
3782
add_group_and_distinct_keys(join, s);
3784
if (!s->const_keys.is_clear_all() &&
3785
!s->table->pos_in_table_list->embedding)
3789
select= make_select(s->table, found_const_table_map,
3790
found_const_table_map,
3791
*s->on_expr_ref ? *s->on_expr_ref : conds,
3795
records= get_quick_record_count(join->session, select, s->table,
3796
&s->const_keys, join->row_limit);
3797
s->quick=select->quick;
3798
s->needed_reg=select->needed_reg;
3800
if (records == 0 && s->table->reginfo.impossible_range)
3803
Impossible WHERE or ON expression
3804
In case of ON, we mark that the we match one empty NULL row.
3805
In case of WHERE, don't set found_const_table_map to get the
3806
caller to abort with a zero row result.
3808
join->const_table_map|= s->table->map;
3809
set_position(join,const_count++,s,(KEYUSE*) 0);
3811
if (*s->on_expr_ref)
3813
/* Generate empty row */
3814
s->info= "Impossible ON condition";
3815
found_const_table_map|= s->table->map;
3817
mark_as_null_row(s->table); // All fields are NULL
3820
if (records != HA_POS_ERROR)
3822
s->found_records=records;
3823
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
3829
join->join_tab=stat;
3830
join->map2table=stat_ref;
3831
join->table= join->all_tables=table_vector;
3832
join->const_tables=const_count;
3833
join->found_const_table_map=found_const_table_map;
3835
/* Find an optimal join order of the non-constant tables. */
3836
if (join->const_tables != join->tables)
3838
optimize_keyuse(join, keyuse_array);
3839
if (choose_plan(join, all_table_map & ~join->const_table_map))
3844
memcpy(join->best_positions, join->positions,
3845
sizeof(POSITION)*join->const_tables);
3846
join->best_read=1.0;
3848
/* Generate an execution plan from the found optimal join order. */
3849
return(join->session->killed || get_best_combination(join));
3853
501
/*****************************************************************************
3854
502
Check with keys are used and with tables references with tables
3855
503
Updates in stat:
3858
506
keyuse Pointer to possible keys
3859
507
*****************************************************************************/
3861
/// Used when finding key fields
3862
typedef struct key_field_t {
3864
Item *val; ///< May be empty if diff constant
3866
uint optimize; // KEY_OPTIMIZE_*
3869
If true, the condition this struct represents will not be satisfied
3872
bool null_rejecting;
3873
bool *cond_guard; /* See KEYUSE::cond_guard */
3874
uint32_t sj_pred_no; /* See KEYUSE::sj_pred_no */
3878
Merge new key definitions to old ones, remove those not used in both.
3880
This is called for OR between different levels.
3882
To be able to do 'ref_or_null' we merge a comparison of a column
3883
and 'column IS NULL' to one test. This is useful for sub select queries
3884
that are internally transformed to something like:.
3887
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
3890
KEY_FIELD::null_rejecting is processed as follows: @n
3891
result has null_rejecting=true if it is set for both ORed references.
3893
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
3894
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
3897
The result of this is that we're missing some 'ref' accesses.
3898
OptimizerTeam: Fix this
3902
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
3905
if (start == new_fields)
3906
return start; // Impossible or
3907
if (new_fields == end)
3908
return start; // No new fields, skip all
3910
KEY_FIELD *first_free=new_fields;
3912
/* Mark all found fields in old array */
3913
for (; new_fields != end ; new_fields++)
3915
for (KEY_FIELD *old=start ; old != first_free ; old++)
3917
if (old->field == new_fields->field)
3920
NOTE: below const_item() call really works as "!used_tables()", i.e.
3921
it can return false where it is feasible to make it return true.
3923
The cause is as follows: Some of the tables are already known to be
3924
const tables (the detection code is in make_join_statistics(),
3925
above the update_ref_and_keys() call), but we didn't propagate
3926
information about this: Table::const_table is not set to true, and
3927
Item::update_used_tables() hasn't been called for each item.
3928
The result of this is that we're missing some 'ref' accesses.
3929
TODO: OptimizerTeam: Fix this
3931
if (!new_fields->val->const_item())
3934
If the value matches, we can use the key reference.
3935
If not, we keep it until we have examined all new values
3937
if (old->val->eq(new_fields->val, old->field->binary()))
3939
old->level= and_level;
3940
old->optimize= ((old->optimize & new_fields->optimize &
3941
KEY_OPTIMIZE_EXISTS) |
3942
((old->optimize | new_fields->optimize) &
3943
KEY_OPTIMIZE_REF_OR_NULL));
3944
old->null_rejecting= (old->null_rejecting &&
3945
new_fields->null_rejecting);
3948
else if (old->eq_func && new_fields->eq_func &&
3949
old->val->eq_by_collation(new_fields->val,
3950
old->field->binary(),
3951
old->field->charset()))
3954
old->level= and_level;
3955
old->optimize= ((old->optimize & new_fields->optimize &
3956
KEY_OPTIMIZE_EXISTS) |
3957
((old->optimize | new_fields->optimize) &
3958
KEY_OPTIMIZE_REF_OR_NULL));
3959
old->null_rejecting= (old->null_rejecting &&
3960
new_fields->null_rejecting);
3962
else if (old->eq_func && new_fields->eq_func &&
3963
((old->val->const_item() && old->val->is_null()) ||
3964
new_fields->val->is_null()))
3966
/* field = expression OR field IS NULL */
3967
old->level= and_level;
3968
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
3970
Remember the NOT NULL value unless the value does not depend
3973
if (!old->val->used_tables() && old->val->is_null())
3974
old->val= new_fields->val;
3975
/* The referred expression can be NULL: */
3976
old->null_rejecting= 0;
3981
We are comparing two different const. In this case we can't
3982
use a key-lookup on this so it's better to remove the value
3983
and let the range optimzier handle it
3985
if (old == --first_free) // If last item
3987
*old= *first_free; // Remove old value
3988
old--; // Retry this value
3993
/* Remove all not used items */
3994
for (KEY_FIELD *old=start ; old != first_free ;)
3996
if (old->level != and_level)
3997
{ // Not used in all levels
3998
if (old == --first_free)
4000
*old= *first_free; // Remove old value
4010
Add a possible key to array of possible keys if it's usable as a key
4012
@param key_fields Pointer to add key, if usable
4013
@param and_level And level, to be stored in KEY_FIELD
4014
@param cond Condition predicate
4015
@param field Field used in comparision
4016
@param eq_func True if we used =, <=> or IS NULL
4017
@param value Value used for comparison with field
4018
@param usable_tables Tables which can be used for key optimization
4019
@param sargables IN/OUT Array of found sargable candidates
4022
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
4023
table, we store this to be able to do not exists optimization later.
4026
*key_fields is incremented if we stored a key in the array
4030
add_key_field(KEY_FIELD **key_fields,uint32_t and_level, Item_func *cond,
4031
Field *field, bool eq_func, Item **value, uint32_t num_values,
4032
table_map usable_tables, SARGABLE_PARAM **sargables)
4034
uint32_t exists_optimize= 0;
4035
if (!(field->flags & PART_KEY_FLAG))
4037
// Don't remove column IS NULL on a LEFT JOIN table
4038
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4039
!field->table->maybe_null || field->null_ptr)
4040
return; // Not a key. Skip it
4041
exists_optimize= KEY_OPTIMIZE_EXISTS;
4042
assert(num_values == 1);
4046
table_map used_tables=0;
4048
for (uint32_t i=0; i<num_values; i++)
4050
used_tables|=(value[i])->used_tables();
4051
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
4056
if (!(usable_tables & field->table->map))
4058
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4059
!field->table->maybe_null || field->null_ptr)
4060
return; // Can't use left join optimize
4061
exists_optimize= KEY_OPTIMIZE_EXISTS;
4065
JOIN_TAB *stat=field->table->reginfo.join_tab;
4066
key_map possible_keys=field->key_start;
4067
possible_keys.intersect(field->table->keys_in_use_for_query);
4068
stat[0].keys.merge(possible_keys); // Add possible keys
4071
Save the following cases:
4073
Field LIKE constant where constant doesn't start with a wildcard
4074
Field = field2 where field2 is in a different table
4081
stat[0].key_dependent|=used_tables;
4084
for (uint32_t i=0; i<num_values; i++)
4086
if (!(is_const&= value[i]->const_item()))
4090
stat[0].const_keys.merge(possible_keys);
4094
Save info to be able check whether this predicate can be
4095
considered as sargable for range analisis after reading const tables.
4096
We do not save info about equalities as update_const_equal_items
4097
will take care of updating info on keys from sargable equalities.
4100
(*sargables)->field= field;
4101
(*sargables)->arg_value= value;
4102
(*sargables)->num_values= num_values;
4105
We can't always use indexes when comparing a string index to a
4106
number. cmp_type() is checked to allow compare of dates to numbers.
4107
eq_func is NEVER true when num_values > 1
4112
Additional optimization: if we're processing
4113
"t.key BETWEEN c1 AND c1" then proceed as if we were processing
4115
TODO: This is a very limited fix. A more generic fix is possible.
4116
There are 2 options:
4117
A) Make equality propagation code be able to handle BETWEEN
4118
(including cases like t1.key BETWEEN t2.key AND t3.key)
4119
B) Make range optimizer to infer additional "t.key = c" equalities
4120
and use them in equality propagation process (see details in
4123
if ((cond->functype() != Item_func::BETWEEN) ||
4124
((Item_func_between*) cond)->negated ||
4125
!value[0]->eq(value[1], field->binary()))
4130
if (field->result_type() == STRING_RESULT)
4132
if ((*value)->result_type() != STRING_RESULT)
4134
if (field->cmp_type() != (*value)->result_type())
4140
We can't use indexes if the effective collation
4141
of the operation differ from the field collation.
4143
if (field->cmp_type() == STRING_RESULT &&
4144
((Field_str*)field)->charset() != cond->compare_collation())
4151
For the moment eq_func is always true. This slot is reserved for future
4152
extensions where we want to remembers other things than just eq comparisons
4155
/* Store possible eq field */
4156
(*key_fields)->field= field;
4157
(*key_fields)->eq_func= eq_func;
4158
(*key_fields)->val= *value;
4159
(*key_fields)->level= and_level;
4160
(*key_fields)->optimize= exists_optimize;
4162
If the condition has form "tbl.keypart = othertbl.field" and
4163
othertbl.field can be NULL, there will be no matches if othertbl.field
4165
We use null_rejecting in add_not_null_conds() to add
4166
'othertbl.field IS NOT NULL' to tab->select_cond.
4168
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
4169
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
4170
((*value)->type() == Item::FIELD_ITEM) &&
4171
((Item_field*)*value)->field->maybe_null());
4172
(*key_fields)->cond_guard= NULL;
4173
(*key_fields)->sj_pred_no= (cond->name >= subq_sj_cond_name &&
4174
cond->name < subq_sj_cond_name + 64)?
4175
cond->name - subq_sj_cond_name: UINT_MAX;
4180
Add possible keys to array of possible keys originated from a simple
4183
@param key_fields Pointer to add key, if usable
4184
@param and_level And level, to be stored in KEY_FIELD
4185
@param cond Condition predicate
4186
@param field Field used in comparision
4187
@param eq_func True if we used =, <=> or IS NULL
4188
@param value Value used for comparison with field
4189
Is NULL for BETWEEN and IN
4190
@param usable_tables Tables which can be used for key optimization
4191
@param sargables IN/OUT Array of found sargable candidates
4194
If field items f1 and f2 belong to the same multiple equality and
4195
a key is added for f1, the the same key is added for f2.
4198
*key_fields is incremented if we stored a key in the array
4202
add_key_equal_fields(KEY_FIELD **key_fields, uint32_t and_level,
4203
Item_func *cond, Item_field *field_item,
4204
bool eq_func, Item **val,
4205
uint32_t num_values, table_map usable_tables,
4206
SARGABLE_PARAM **sargables)
4208
Field *field= field_item->field;
4209
add_key_field(key_fields, and_level, cond, field,
4210
eq_func, val, num_values, usable_tables, sargables);
4211
Item_equal *item_equal= field_item->item_equal;
4215
Add to the set of possible key values every substitution of
4216
the field for an equal field included into item_equal
4218
Item_equal_iterator it(*item_equal);
4220
while ((item= it++))
4222
if (!field->eq(item->field))
4224
add_key_field(key_fields, and_level, cond, item->field,
4225
eq_func, val, num_values, usable_tables,
4233
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint32_t *and_level,
4234
COND *cond, table_map usable_tables,
4235
SARGABLE_PARAM **sargables)
4237
if (cond->type() == Item_func::COND_ITEM)
4239
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
4240
KEY_FIELD *org_key_fields= *key_fields;
4242
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
4246
add_key_fields(join, key_fields, and_level, item, usable_tables,
4248
for (; org_key_fields != *key_fields ; org_key_fields++)
4249
org_key_fields->level= *and_level;
4254
add_key_fields(join, key_fields, and_level, li++, usable_tables,
4259
KEY_FIELD *start_key_fields= *key_fields;
4261
add_key_fields(join, key_fields, and_level, item, usable_tables,
4263
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
4264
*key_fields,++(*and_level));
4271
Subquery optimization: Conditions that are pushed down into subqueries
4272
are wrapped into Item_func_trig_cond. We process the wrapped condition
4273
but need to set cond_guard for KEYUSE elements generated from it.
4276
if (cond->type() == Item::FUNC_ITEM &&
4277
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
4279
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
4280
if (!join->group_list && !join->order &&
4282
join->unit->item->substype() == Item_subselect::IN_SUBS &&
4283
!join->unit->is_union())
4285
KEY_FIELD *save= *key_fields;
4286
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
4288
// Indicate that this ref access candidate is for subquery lookup:
4289
for (; save != *key_fields; save++)
4290
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
4296
/* If item is of type 'field op field/constant' add it to key_fields */
4297
if (cond->type() != Item::FUNC_ITEM)
4299
Item_func *cond_func= (Item_func*) cond;
4300
switch (cond_func->select_optimize()) {
4301
case Item_func::OPTIMIZE_NONE:
4303
case Item_func::OPTIMIZE_KEY:
4307
if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
4308
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4310
values= cond_func->arguments()+1;
4311
if (cond_func->functype() == Item_func::NE_FUNC &&
4312
cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4313
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4315
assert(cond_func->functype() != Item_func::IN_FUNC ||
4316
cond_func->argument_count() != 2);
4317
add_key_equal_fields(key_fields, *and_level, cond_func,
4318
(Item_field*) (cond_func->key_item()->real_item()),
4320
cond_func->argument_count()-1,
4321
usable_tables, sargables);
4323
if (cond_func->functype() == Item_func::BETWEEN)
4325
values= cond_func->arguments();
4326
for (uint32_t i= 1 ; i < cond_func->argument_count() ; i++)
4328
Item_field *field_item;
4329
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
4331
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
4333
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
4334
add_key_equal_fields(key_fields, *and_level, cond_func,
4335
field_item, 0, values, 1, usable_tables,
4342
case Item_func::OPTIMIZE_OP:
4344
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
4345
cond_func->functype() == Item_func::EQUAL_FUNC);
4347
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4348
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4350
add_key_equal_fields(key_fields, *and_level, cond_func,
4351
(Item_field*) (cond_func->arguments()[0])->real_item(),
4353
cond_func->arguments()+1, 1, usable_tables,
4356
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4357
cond_func->functype() != Item_func::LIKE_FUNC &&
4358
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
4360
add_key_equal_fields(key_fields, *and_level, cond_func,
4361
(Item_field*) (cond_func->arguments()[1])->real_item(),
4363
cond_func->arguments(),1,usable_tables,
4368
case Item_func::OPTIMIZE_NULL:
4369
/* column_name IS [NOT] NULL */
4370
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4371
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4373
Item *tmp=new Item_null;
4374
if (unlikely(!tmp)) // Should never be true
4376
add_key_equal_fields(key_fields, *and_level, cond_func,
4377
(Item_field*) (cond_func->arguments()[0])->real_item(),
4378
cond_func->functype() == Item_func::ISNULL_FUNC,
4379
&tmp, 1, usable_tables, sargables);
4382
case Item_func::OPTIMIZE_EQUAL:
4383
Item_equal *item_equal= (Item_equal *) cond;
4384
Item *const_item= item_equal->get_const();
4385
Item_equal_iterator it(*item_equal);
4390
For each field field1 from item_equal consider the equality
4391
field1=const_item as a condition allowing an index access of the table
4392
with field1 by the keys value of field1.
4394
while ((item= it++))
4396
add_key_field(key_fields, *and_level, cond_func, item->field,
4397
true, &const_item, 1, usable_tables, sargables);
4403
Consider all pairs of different fields included into item_equal.
4404
For each of them (field1, field1) consider the equality
4405
field1=field2 as a condition allowing an index access of the table
4406
with field1 by the keys value of field2.
4408
Item_equal_iterator fi(*item_equal);
4409
while ((item= fi++))
4411
Field *field= item->field;
4412
while ((item= it++))
4414
if (!field->eq(item->field))
4416
add_key_field(key_fields, *and_level, cond_func, field,
4417
true, (Item **) &item, 1, usable_tables,
4429
511
Add all keys with uses 'field' for some keypart.
4431
513
If field->and_level != and_level then only mark key_part as const_part.
4435
max_part_bit(key_part_map bits)
515
uint32_t max_part_bit(key_part_map bits)
4438
518
for (found=0; bits & 1 ; found++,bits>>=1) ;
4443
add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
4445
Field *field=key_field->field;
4446
Table *form= field->table;
4449
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
4451
for (uint32_t key= 0 ; key < form->sizeKeys() ; key++)
4453
if (!(form->keys_in_use_for_query.is_set(key)))
4456
uint32_t key_parts= (uint) form->key_info[key].key_parts;
4457
for (uint32_t part=0 ; part < key_parts ; part++)
4459
if (field->eq(form->key_info[key].key_part[part].field))
4461
keyuse.table= field->table;
4462
keyuse.val = key_field->val;
4464
keyuse.keypart=part;
4465
keyuse.keypart_map= (key_part_map) 1 << part;
4466
keyuse.used_tables=key_field->val->used_tables();
4467
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
4468
keyuse.null_rejecting= key_field->null_rejecting;
4469
keyuse.cond_guard= key_field->cond_guard;
4470
keyuse.sj_pred_no= key_field->sj_pred_no;
4471
insert_dynamic(keyuse_array,(unsigned char*) &keyuse);
4479
sort_keyuse(KEYUSE *a,KEYUSE *b)
523
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)
4482
if (a->table->tablenr != b->table->tablenr)
4483
return (int) (a->table->tablenr - b->table->tablenr);
4484
if (a->key != b->key)
4485
return (int) (a->key - b->key);
4486
if (a->keypart != b->keypart)
4487
return (int) (a->keypart - b->keypart);
526
if (a->getTable()->tablenr != b->getTable()->tablenr)
527
return static_cast<int>((a->getTable()->tablenr - b->getTable()->tablenr));
529
if (a->getKey() != b->getKey())
530
return static_cast<int>((a->getKey() - b->getKey()));
532
if (a->getKeypart() != b->getKeypart())
533
return static_cast<int>((a->getKeypart() - b->getKeypart()));
4488
535
// Place const values before other ones
4489
if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
4490
test((b->used_tables & ~OUTER_REF_TABLE_BIT))))
536
if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -
537
test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))
4492
540
/* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
4493
return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
4494
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
4499
Add to KEY_FIELD array all 'ref' access candidates within nested join.
4501
This function populates KEY_FIELD array with entries generated from the
4502
ON condition of the given nested join, and does the same for nested joins
4503
contained within this nested join.
4505
@param[in] nested_join_table Nested join pseudo-table to process
4506
@param[in,out] end End of the key field array
4507
@param[in,out] and_level And-level
4508
@param[in,out] sargables Array of found sargable candidates
4512
We can add accesses to the tables that are direct children of this nested
4513
join (1), and are not inner tables w.r.t their neighbours (2).
4515
Example for #1 (outer brackets pair denotes nested join this function is
4518
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
4522
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
4524
In examples 1-2 for condition cond, we can add 'ref' access candidates to
4528
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
4530
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
4533
static void add_key_fields_for_nj(JOIN *join, TableList *nested_join_table,
4534
KEY_FIELD **end, uint32_t *and_level,
4535
SARGABLE_PARAM **sargables)
4537
List_iterator<TableList> li(nested_join_table->nested_join->join_list);
4538
List_iterator<TableList> li2(nested_join_table->nested_join->join_list);
4539
bool have_another = false;
4540
table_map tables= 0;
4542
assert(nested_join_table->nested_join);
4544
while ((table= li++) || (have_another && (li=li2, have_another=false,
4547
if (table->nested_join)
4549
if (!table->on_expr)
4551
/* It's a semi-join nest. Walk into it as if it wasn't a nest */
4554
li= List_iterator<TableList>(table->nested_join->join_list);
4557
add_key_fields_for_nj(join, table, end, and_level, sargables);
4560
if (!table->on_expr)
4561
tables |= table->table->map;
4563
if (nested_join_table->on_expr)
4564
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
541
return static_cast<int>(((a->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) -
542
(b->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)));
4799
add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab)
772
void add_group_and_distinct_keys(Join *join, JoinTable *join_tab)
4801
774
List<Item_field> indexed_fields;
4802
List_iterator<Item_field> indexed_fields_it(indexed_fields);
4803
order_st *cur_group;
775
List<Item_field>::iterator indexed_fields_it(indexed_fields.begin());
4804
777
Item_field *cur_item;
4805
778
key_map possible_keys(0);
4807
780
if (join->group_list)
4808
781
{ /* Collect all query fields referenced in the GROUP clause. */
4809
782
for (cur_group= join->group_list; cur_group; cur_group= cur_group->next)
4810
(*cur_group->item)->walk(&Item::collect_item_field_processor, 0,
4811
(unsigned char*) &indexed_fields);
784
(*cur_group->item)->walk(&Item::collect_item_field_processor, 0, (unsigned char*) &indexed_fields);
4813
787
else if (join->select_distinct)
4814
788
{ /* Collect all query fields referenced in the SELECT clause. */
4815
789
List<Item> &select_items= join->fields_list;
4816
List_iterator<Item> select_items_it(select_items);
790
List<Item>::iterator select_items_it(select_items.begin());
4818
792
while ((item= select_items_it++))
4819
item->walk(&Item::collect_item_field_processor, 0,
4820
(unsigned char*) &indexed_fields);
794
item->walk(&Item::collect_item_field_processor, 0, (unsigned char*) &indexed_fields);
4825
if (indexed_fields.elements == 0)
802
if (indexed_fields.size() == 0)
4828
807
/* Intersect the keys of all group fields. */
4829
808
cur_item= indexed_fields_it++;
4830
possible_keys.merge(cur_item->field->part_of_key);
809
possible_keys|= cur_item->field->part_of_key;
4831
810
while ((cur_item= indexed_fields_it++))
4833
possible_keys.intersect(cur_item->field->part_of_key);
4836
if (!possible_keys.is_clear_all())
4837
join_tab->const_keys.merge(possible_keys);
4841
/*****************************************************************************
4842
Go through all combinations of not marked tables and find the one
4843
which uses least records
4844
*****************************************************************************/
4846
/** Save const tables first as used tables. */
4849
set_position(JOIN *join,uint32_t idx,JOIN_TAB *table,KEYUSE *key)
4851
join->positions[idx].table= table;
4852
join->positions[idx].key=key;
4853
join->positions[idx].records_read=1.0; /* This is a const table */
4854
join->positions[idx].ref_depend_map= 0;
4856
/* Move the const table as down as possible in best_ref */
4857
JOIN_TAB **pos=join->best_ref+idx+1;
4858
JOIN_TAB *next=join->best_ref[idx];
4859
for (;next != table ; pos++)
4861
JOIN_TAB *tmp=pos[0];
4865
join->best_ref[idx]=table;
4870
Given a semi-join nest, find out which of the IN-equalities are bound
4873
get_bound_sj_equalities()
4874
sj_nest Semi-join nest
4875
remaining_tables Tables that are not yet bound
4878
Given a semi-join nest, find out which of the IN-equalities have their
4879
left part expression bound (i.e. the said expression doesn't refer to
4880
any of remaining_tables and can be evaluated).
4883
Bitmap of bound IN-equalities.
4886
uint64_t get_bound_sj_equalities(TableList *sj_nest,
4887
table_map remaining_tables)
4889
List_iterator<Item> li(sj_nest->nested_join->sj_outer_expr_list);
4893
while ((item= li++))
4896
Q: should this take into account equality propagation and how?
4897
A: If e->outer_side is an Item_field, walk over the equality
4898
class and see if there is an element that is bound?
4899
(this is an optional feature)
4901
if (!(item->used_tables() & remaining_tables))
4911
Find the best access path for an extension of a partial execution
4912
plan and add this path to the plan.
4914
The function finds the best access path to table 's' from the passed
4915
partial plan where an access path is the general term for any means to
4916
access the data in 's'. An access path may use either an index or a scan,
4917
whichever is cheaper. The input partial plan is passed via the array
4918
'join->positions' of length 'idx'. The chosen access method for 's' and its
4919
cost are stored in 'join->positions[idx]'.
4921
@param join pointer to the structure providing all context info
4923
@param s the table to be joined by the function
4924
@param session thread for the connection that submitted the query
4925
@param remaining_tables set of tables not included into the partial plan yet
4926
@param idx the length of the partial plan
4927
@param record_count estimate for the number of records returned by the
4929
@param read_time the cost of the partial plan
4936
best_access_path(JOIN *join,
4939
table_map remaining_tables,
4941
double record_count,
4944
KEYUSE *best_key= 0;
4945
uint32_t best_max_key_part= 0;
4946
bool found_constraint= 0;
4947
double best= DBL_MAX;
4948
double best_time= DBL_MAX;
4949
double records= DBL_MAX;
4950
table_map best_ref_depends_map= 0;
4953
uint32_t best_is_sj_inside_out= 0;
4956
{ /* Use key if possible */
4957
Table *table= s->table;
4958
KEYUSE *keyuse,*start_key=0;
4959
double best_records= DBL_MAX;
4960
uint32_t max_key_part=0;
4961
uint64_t bound_sj_equalities= 0;
4962
bool try_sj_inside_out= false;
4964
Discover the bound equalites. We need to do this, if
4965
1. The next table is an SJ-inner table, and
4966
2. It is the first table from that semijoin, and
4967
3. We're not within a semi-join range (i.e. all semi-joins either have
4968
all or none of their tables in join_table_map), except
4969
s->emb_sj_nest (which we've just entered).
4970
3. All correlation references from this sj-nest are bound
4972
if (s->emb_sj_nest && // (1)
4973
s->emb_sj_nest->sj_in_exprs < 64 &&
4974
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
4975
s->emb_sj_nest->sj_inner_tables) && // (2)
4976
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
4977
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
4979
/* This table is an InsideOut scan candidate */
4980
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
4982
try_sj_inside_out= true;
4985
/* Test how we can use keys */
4986
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
4987
for (keyuse=s->keyuse ; keyuse->table == table ;)
4989
key_part_map found_part= 0;
4990
table_map found_ref= 0;
4991
uint32_t key= keyuse->key;
4992
KEY *keyinfo= table->key_info+key;
4993
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
4994
key_part_map const_part= 0;
4995
/* The or-null keypart in ref-or-null access: */
4996
key_part_map ref_or_null_part= 0;
4998
/* Calculate how many key segments of the current key we can use */
5000
uint64_t handled_sj_equalities=0;
5001
key_part_map sj_insideout_map= 0;
5003
do /* For each keypart */
5005
uint32_t keypart= keyuse->keypart;
5006
table_map best_part_found_ref= 0;
5007
double best_prev_record_reads= DBL_MAX;
5009
do /* For each way to access the keypart */
5013
if 1. expression doesn't refer to forward tables
5014
2. we won't get two ref-or-null's
5016
if (!(remaining_tables & keyuse->used_tables) &&
5017
!(ref_or_null_part && (keyuse->optimize &
5018
KEY_OPTIMIZE_REF_OR_NULL)))
5020
found_part|= keyuse->keypart_map;
5021
if (!(keyuse->used_tables & ~join->const_table_map))
5022
const_part|= keyuse->keypart_map;
5024
double tmp2= prev_record_reads(join, idx, (found_ref |
5025
keyuse->used_tables));
5026
if (tmp2 < best_prev_record_reads)
5028
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
5029
best_prev_record_reads= tmp2;
5031
if (rec > keyuse->ref_table_rows)
5032
rec= keyuse->ref_table_rows;
5034
If there is one 'key_column IS NULL' expression, we can
5035
use this ref_or_null optimisation of this field
5037
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
5038
ref_or_null_part |= keyuse->keypart_map;
5041
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
5043
if (!(remaining_tables & keyuse->used_tables))
5044
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
5047
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
5048
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
5053
} while (keyuse->table == table && keyuse->key == key &&
5054
keyuse->keypart == keypart);
5055
found_ref|= best_part_found_ref;
5056
} while (keyuse->table == table && keyuse->key == key);
5059
Assume that that each key matches a proportional part of table.
5061
if (!found_part && !handled_sj_equalities)
5062
continue; // Nothing usable found
5064
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
5065
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
5067
bool sj_inside_out_scan= false;
5069
found_constraint= 1;
5071
Check if InsideOut scan is applicable:
5072
1. All IN-equalities are either "bound" or "handled"
5073
2. Index keyparts are
5076
if (try_sj_inside_out &&
5077
table->covering_keys.is_set(key) &&
5078
(handled_sj_equalities | bound_sj_equalities) == // (1)
5079
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
5081
uint32_t n_fixed_parts= max_part_bit(found_part);
5082
if (n_fixed_parts != keyinfo->key_parts &&
5083
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
5084
PREV_BITS(uint, keyinfo->key_parts))
5087
Not all parts are fixed. Produce bitmap of remaining bits and
5088
check if all of them are covered.
5090
sj_inside_out_scan= true;
5094
It's a confluent ref scan.
5096
That is, all found KEYUSE elements refer to IN-equalities,
5097
and there is really no ref access because there is no
5098
t.keypart0 = {bound expression}
5100
Calculate the cost of complete loose index scan.
5102
records= (double)s->table->file->stats.records;
5104
/* The cost is entire index scan cost (divided by 2) */
5105
best_time= s->table->file->index_only_read_time(key, records);
5107
/* Now figure how many different keys we will get */
5109
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
5110
records= records / rpc;
5117
Check if we found full key
5119
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
5122
max_key_part= UINT32_MAX;
5123
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
5125
tmp = prev_record_reads(join, idx, found_ref);
5131
{ /* We found a const key */
5133
ReuseRangeEstimateForRef-1:
5134
We get here if we've found a ref(const) (c_i are constants):
5135
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
5137
If range optimizer was able to construct a "range"
5138
access on this index, then its condition "quick_cond" was
5139
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
5140
from the range optimizer.
5142
Proof of (*): By properties of range and ref optimizers
5143
quick_cond will be equal or tighther than ref_const_cond.
5144
ref_const_cond already covers "smallest" possible interval -
5145
a singlepoint interval over all keyparts. Therefore,
5146
quick_cond is equivalent to ref_const_cond (if it was an
5147
empty interval we wouldn't have got here).
5149
if (table->quick_keys.is_set(key))
5150
records= (double) table->quick_rows[key];
5153
/* quick_range couldn't use key! */
5154
records= (double) s->records/rec;
5159
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
5160
{ /* Prefer longer keys */
5162
((double) s->records / (double) rec *
5164
((double) (table->s->max_key_length-keyinfo->key_length) /
5165
(double) table->s->max_key_length)));
5167
records=2.0; /* Can't be as good as a unique */
5170
ReuseRangeEstimateForRef-2: We get here if we could not reuse
5171
E(#rows) from range optimizer. Make another try:
5173
If range optimizer produced E(#rows) for a prefix of the ref
5174
access we're considering, and that E(#rows) is lower then our
5175
current estimate, make an adjustment. The criteria of when we
5176
can make an adjustment is a special case of the criteria used
5177
in ReuseRangeEstimateForRef-3.
5179
if (table->quick_keys.is_set(key) &&
5180
const_part & (1 << table->quick_key_parts[key]) &&
5181
table->quick_n_ranges[key] == 1 &&
5182
records > (double) table->quick_rows[key])
5184
records= (double) table->quick_rows[key];
5187
/* Limit the number of matched rows */
5189
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5190
if (table->covering_keys.is_set(key))
5192
/* we can use only index tree */
5193
tmp= record_count * table->file->index_only_read_time(key, tmp);
5196
tmp= record_count*cmin(tmp,s->worst_seeks);
5202
Use as much key-parts as possible and a uniq key is better
5203
than a not unique key
5204
Set tmp to (previous record count) * (records / combination)
5206
if ((found_part & 1) &&
5207
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
5208
found_part == PREV_BITS(uint,keyinfo->key_parts)))
5210
max_key_part= max_part_bit(found_part);
5212
ReuseRangeEstimateForRef-3:
5213
We're now considering a ref[or_null] access via
5214
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
5215
(same-as-above but with one cond replaced
5216
with "t.keypart_i IS NULL")] (**)
5218
Try re-using E(#rows) from "range" optimizer:
5219
We can do so if "range" optimizer used the same intervals as
5220
in (**). The intervals used by range optimizer may be not
5221
available at this point (as "range" access might have choosen to
5222
create quick select over another index), so we can't compare
5223
them to (**). We'll make indirect judgements instead.
5224
The sufficient conditions for re-use are:
5225
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
5226
this is not satisfied we have no way to know which ranges
5227
will be actually scanned by 'ref' until we execute the
5229
(C2) max #key parts in 'range' access == K == max_key_part (this
5230
is apparently a necessary requirement)
5232
We also have a property that "range optimizer produces equal or
5233
tighter set of scan intervals than ref(const) optimizer". Each
5234
of the intervals in (**) are "tightest possible" intervals when
5235
one limits itself to using keyparts 1..K (which we do in #2).
5236
From here it follows that range access used either one, or
5237
both of the (I1) and (I2) intervals:
5239
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
5240
(same-as-above but with one cond replaced
5241
with "t.keypart_i IS NULL") (I2)
5243
The remaining part is to exclude the situation where range
5244
optimizer used one interval while we're considering
5245
ref-or-null and looking for estimate for two intervals. This
5246
is done by last limitation:
5248
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
5250
if (table->quick_keys.is_set(key) && !found_ref && //(C1)
5251
table->quick_key_parts[key] == max_key_part && //(C2)
5252
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
5254
tmp= records= (double) table->quick_rows[key];
5258
/* Check if we have statistic about the distribution */
5259
if ((records= keyinfo->rec_per_key[max_key_part-1]))
5262
Fix for the case where the index statistics is too
5264
(1) We're considering ref(const) and there is quick select
5266
(2) and that quick select uses more keyparts (i.e. it will
5267
scan equal/smaller interval then this ref(const))
5268
(3) and E(#rows) for quick select is higher then our
5271
We'll use E(#rows) from quick select.
5273
Q: Why do we choose to use 'ref'? Won't quick select be
5274
cheaper in some cases ?
5275
TODO: figure this out and adjust the plan choice if needed.
5277
if (!found_ref && table->quick_keys.is_set(key) && // (1)
5278
table->quick_key_parts[key] > max_key_part && // (2)
5279
records < (double)table->quick_rows[key]) // (3)
5280
records= (double)table->quick_rows[key];
5287
Assume that the first key part matches 1% of the file
5288
and that the whole key matches 10 (duplicates) or 1
5290
Assume also that more key matches proportionally more
5292
This gives the formula:
5293
records = (x * (b-a) + a*c-b)/(c-1)
5295
b = records matched by whole key
5296
a = records matched by first key part (1% of all records?)
5297
c = number of key parts in key
5298
x = used key parts (1 <= x <= c)
5301
if (!(rec_per_key=(double)
5302
keyinfo->rec_per_key[keyinfo->key_parts-1]))
5303
rec_per_key=(double) s->records/rec+1;
5307
else if (rec_per_key/(double) s->records >= 0.01)
5311
double a=s->records*0.01;
5312
if (keyinfo->key_parts > 1)
5313
tmp= (max_key_part * (rec_per_key - a) +
5314
a*keyinfo->key_parts - rec_per_key)/
5315
(keyinfo->key_parts-1);
5318
set_if_bigger(tmp,1.0);
5320
records = (uint32_t) tmp;
5323
if (ref_or_null_part)
5325
/* We need to do two key searches to find key */
5331
ReuseRangeEstimateForRef-4: We get here if we could not reuse
5332
E(#rows) from range optimizer. Make another try:
5334
If range optimizer produced E(#rows) for a prefix of the ref
5335
access we're considering, and that E(#rows) is lower then our
5336
current estimate, make the adjustment.
5338
The decision whether we can re-use the estimate from the range
5339
optimizer is the same as in ReuseRangeEstimateForRef-3,
5340
applied to first table->quick_key_parts[key] key parts.
5342
if (table->quick_keys.is_set(key) &&
5343
table->quick_key_parts[key] <= max_key_part &&
5344
const_part & (1 << table->quick_key_parts[key]) &&
5345
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
5346
const_part) ? 1 : 0) &&
5347
records > (double) table->quick_rows[key])
5349
tmp= records= (double) table->quick_rows[key];
5353
/* Limit the number of matched rows */
5354
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5355
if (table->covering_keys.is_set(key))
5357
/* we can use only index tree */
5358
tmp= record_count * table->file->index_only_read_time(key, tmp);
5361
tmp= record_count * cmin(tmp,s->worst_seeks);
5364
tmp= best_time; // Do nothing
5367
if (sj_inside_out_scan && !start_key)
5375
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
5377
best_time= tmp + records/(double) TIME_FOR_COMPARE;
5379
best_records= records;
5380
best_key= start_key;
5381
best_max_key_part= max_key_part;
5382
best_ref_depends_map= found_ref;
5383
best_is_sj_inside_out= sj_inside_out_scan;
5386
records= best_records;
5390
Don't test table scan if it can't be better.
5391
Prefer key lookup if we would use the same key for scanning.
5393
Don't do a table scan on InnoDB tables, if we can read the used
5394
parts of the row from any of the used index.
5395
This is because table scans uses index and we would not win
5396
anything by using a table scan.
5398
A word for word translation of the below if-statement in sergefp's
5399
understanding: we check if we should use table scan if:
5400
(1) The found 'ref' access produces more records than a table scan
5401
(or index scan, or quick select), or 'ref' is more expensive than
5403
(2) This doesn't hold: the best way to perform table scan is to to perform
5404
'range' access using index IDX, and the best way to perform 'ref'
5405
access is to use the same index IDX, with the same or more key parts.
5406
(note: it is not clear how this rule is/should be extended to
5407
index_merge quick selects)
5408
(3) See above note about InnoDB.
5409
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
5410
path, but there is no quick select)
5411
If the condition in the above brackets holds, then the only possible
5412
"table scan" access method is ALL/index (there is no quick select).
5413
Since we have a 'ref' access path, and FORCE INDEX instructs us to
5414
choose it over ALL/index, there is no need to consider a full table
5417
if ((records >= s->found_records || best > s->read_time) && // (1)
5418
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
5419
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
5420
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
5421
! s->table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
5422
!(s->table->force_index && best_key && !s->quick)) // (4)
5423
{ // Check full join
5424
ha_rows rnd_records= s->found_records;
5426
If there is a filtering condition on the table (i.e. ref analyzer found
5427
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
5428
preceding this table in the join order we're now considering), then
5429
assume that 25% of the rows will be filtered out by this condition.
5431
This heuristic is supposed to force tables used in exprZ to be before
5432
this table in join order.
5434
if (found_constraint)
5435
rnd_records-= rnd_records/4;
5438
If applicable, get a more accurate estimate. Don't use the two
5441
if (s->table->quick_condition_rows != s->found_records)
5442
rnd_records= s->table->quick_condition_rows;
5445
Range optimizer never proposes a RANGE if it isn't better
5446
than FULL: so if RANGE is present, it's always preferred to FULL.
5447
Here we estimate its cost.
5453
- read record range through 'quick'
5454
- skip rows which does not satisfy WHERE constraints
5456
We take into account possible use of join cache for ALL/index
5457
access (see first else-branch below), but we don't take it into
5458
account here for range/index_merge access. Find out why this is so.
5461
(s->quick->read_time +
5462
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
5466
/* Estimate cost of reading table. */
5467
tmp= s->table->file->scan_time();
5468
if (s->table->map & join->outer_join) // Can't use join cache
5471
For each record we have to:
5472
- read the whole table record
5473
- skip rows which does not satisfy join condition
5477
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
5481
/* We read the table as many times as join buffer becomes full. */
5482
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
5484
(double) session->variables.join_buff_size));
5486
We don't make full cartesian product between rows in the scanned
5487
table and existing records because we skip all rows from the
5488
scanned table, which does not satisfy join condition when
5489
we read the table (see flush_cached_records for details). Here we
5490
take into account cost to read and skip these records.
5492
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
5497
We estimate the cost of evaluating WHERE clause for found records
5498
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
5499
tmp give us total cost of using Table SCAN
5501
if (best == DBL_MAX ||
5502
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
5503
best + record_count/(double) TIME_FOR_COMPARE*records))
5506
If the table has a range (s->quick is set) make_join_select()
5507
will ensure that this will be used
5510
records= rows2double(rnd_records);
5512
/* range/index_merge/ALL/index access method are "independent", so: */
5513
best_ref_depends_map= 0;
5514
best_is_sj_inside_out= false;
5518
/* Update the cost information for the current partial plan */
5519
join->positions[idx].records_read= records;
5520
join->positions[idx].read_time= best;
5521
join->positions[idx].key= best_key;
5522
join->positions[idx].table= s;
5523
join->positions[idx].ref_depend_map= best_ref_depends_map;
5524
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
5527
idx == join->const_tables &&
5528
s->table == join->sort_by_table &&
5529
join->unit->select_limit_cnt >= records)
5530
join->sort_by_table= (Table*) 1; // Must use temporary table
5537
Selects and invokes a search strategy for an optimal query plan.
5539
The function checks user-configurable parameters that control the search
5540
strategy for an optimal plan, selects the search method and then invokes
5541
it. Each specific optimization procedure stores the final optimal plan in
5542
the array 'join->best_positions', and the cost of the plan in
5545
@param join pointer to the structure providing all context info for
5547
@param join_tables set of the tables in the query
5550
'MAX_TABLES+2' denotes the old implementation of find_best before
5551
the greedy version. Will be removed when greedy_search is approved.
5560
choose_plan(JOIN *join, table_map join_tables)
5562
uint32_t search_depth= join->session->variables.optimizer_search_depth;
5563
uint32_t prune_level= join->session->variables.optimizer_prune_level;
5564
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
5566
join->cur_embedding_map= 0;
5567
reset_nj_counters(join->join_list);
5569
if (SELECT_STRAIGHT_JOIN option is set)
5570
reorder tables so dependent tables come after tables they depend
5571
on, otherwise keep tables in the order they were specified in the query
5573
Apply heuristic: pre-sort all access plans with respect to the number of
5576
my_qsort(join->best_ref + join->const_tables,
5577
join->tables - join->const_tables, sizeof(JOIN_TAB*),
5578
straight_join ? join_tab_cmp_straight : join_tab_cmp);
5579
join->cur_emb_sj_nests= 0;
5582
optimize_straight_join(join, join_tables);
5586
if (search_depth == MAX_TABLES+2)
5588
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
5589
the greedy version. Will be removed when greedy_search is approved.
5591
join->best_read= DBL_MAX;
5592
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
5597
if (search_depth == 0)
5598
/* Automatically determine a reasonable value for 'search_depth' */
5599
search_depth= determine_search_depth(join);
5600
if (greedy_search(join, join_tables, search_depth, prune_level))
5606
Store the cost of this query into a user variable
5607
Don't update last_query_cost for statements that are not "flat joins" :
5608
i.e. they have subqueries, unions or call stored procedures.
5609
TODO: calculate a correct cost for a query with subqueries and UNIONs.
5611
if (join->session->lex->is_single_level_stmt())
5612
join->session->status_var.last_query_cost= join->best_read;
5618
Compare two JOIN_TAB objects based on the number of accessed records.
5620
@param ptr1 pointer to first JOIN_TAB object
5621
@param ptr2 pointer to second JOIN_TAB object
812
possible_keys&= cur_item->field->part_of_key;
815
if (possible_keys.any())
816
join_tab->const_keys|= possible_keys;
820
Compare two JoinTable objects based on the number of accessed records.
822
@param ptr1 pointer to first JoinTable object
823
@param ptr2 pointer to second JoinTable object
5624
826
The order relation implemented by join_tab_cmp() is not transitive,
5643
join_tab_cmp(const void* ptr1, const void* ptr2)
843
int join_tab_cmp(const void* ptr1, const void* ptr2)
5645
JOIN_TAB *jt1= *(JOIN_TAB**) ptr1;
5646
JOIN_TAB *jt2= *(JOIN_TAB**) ptr2;
845
JoinTable *jt1= *(JoinTable**) ptr1;
846
JoinTable *jt2= *(JoinTable**) ptr2;
5648
848
if (jt1->dependent & jt2->table->map)
5650
851
if (jt2->dependent & jt1->table->map)
5652
854
if (jt1->found_records > jt2->found_records)
5654
857
if (jt1->found_records < jt2->found_records)
5656
860
return jt1 > jt2 ? 1 : (jt1 < jt2 ? -1 : 0);
5661
864
Same as join_tab_cmp, but for use with SELECT_STRAIGHT_JOIN.
5665
join_tab_cmp_straight(const void* ptr1, const void* ptr2)
866
int join_tab_cmp_straight(const void* ptr1, const void* ptr2)
5667
JOIN_TAB *jt1= *(JOIN_TAB**) ptr1;
5668
JOIN_TAB *jt2= *(JOIN_TAB**) ptr2;
868
JoinTable *jt1= *(JoinTable**) ptr1;
869
JoinTable *jt2= *(JoinTable**) ptr2;
5670
871
if (jt1->dependent & jt2->table->map)
5672
874
if (jt2->dependent & jt1->table->map)
5674
877
return jt1 > jt2 ? 1 : (jt1 < jt2 ? -1 : 0);
5678
Heuristic procedure to automatically guess a reasonable degree of
5679
exhaustiveness for the greedy search procedure.
5681
The procedure estimates the optimization time and selects a search depth
5682
big enough to result in a near-optimal QEP, that doesn't take too long to
5683
find. If the number of tables in the query exceeds some constant, then
5684
search_depth is set to this constant.
5686
@param join pointer to the structure providing all context info for
5690
This is an extremely simplistic implementation that serves as a stub for a
5691
more advanced analysis of the join. Ideally the search depth should be
5692
determined by learning from previous query optimizations, because it will
5693
depend on the CPU power (and other factors).
5696
this value should be determined dynamically, based on statistics:
5697
uint32_t max_tables_for_exhaustive_opt= 7;
5700
this value could be determined by some mapping of the form:
5701
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5704
A positive integer that specifies the search depth (and thus the
5705
exhaustiveness) of the depth-first search algorithm used by
5710
determine_search_depth(JOIN *join)
5712
uint32_t table_count= join->tables - join->const_tables;
5713
uint32_t search_depth;
5714
/* TODO: this value should be determined dynamically, based on statistics: */
5715
uint32_t max_tables_for_exhaustive_opt= 7;
5717
if (table_count <= max_tables_for_exhaustive_opt)
5718
search_depth= table_count+1; // use exhaustive for small number of tables
5721
TODO: this value could be determined by some mapping of the form:
5722
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5724
search_depth= max_tables_for_exhaustive_opt; // use greedy search
5726
return search_depth;
5731
Select the best ways to access the tables in a query without reordering them.
5733
Find the best access paths for each query table and compute their costs
5734
according to their order in the array 'join->best_ref' (thus without
5735
reordering the join tables). The function calls sequentially
5736
'best_access_path' for each table in the query to select the best table
5737
access method. The final optimal plan is stored in the array
5738
'join->best_positions', and the corresponding cost in 'join->best_read'.
5740
@param join pointer to the structure providing all context info for
5742
@param join_tables set of the tables in the query
5745
This function can be applied to:
5746
- queries with STRAIGHT_JOIN
5747
- internally to compute the cost of an arbitrary QEP
5749
Thus 'optimize_straight_join' can be used at any stage of the query
5750
optimization process to finalize a QEP as it is.
5754
optimize_straight_join(JOIN *join, table_map join_tables)
5757
uint32_t idx= join->const_tables;
5758
double record_count= 1.0;
5759
double read_time= 0.0;
5761
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
5763
/* Find the best access method from 's' to the current partial plan */
5764
advance_sj_state(join_tables, s);
5765
best_access_path(join, s, join->session, join_tables, idx,
5766
record_count, read_time);
5767
/* compute the cost of the new plan extended with 's' */
5768
record_count*= join->positions[idx].records_read;
5769
read_time+= join->positions[idx].read_time;
5770
join_tables&= ~(s->table->map);
5774
read_time+= record_count / (double) TIME_FOR_COMPARE;
5775
if (join->sort_by_table &&
5776
join->sort_by_table != join->positions[join->const_tables].table->table)
5777
read_time+= record_count; // We have to make a temp table
5778
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
5779
join->best_read= read_time;
5784
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
5786
The search procedure uses a hybrid greedy/exhaustive search with controlled
5787
exhaustiveness. The search is performed in N = card(remaining_tables)
5788
steps. Each step evaluates how promising is each of the unoptimized tables,
5789
selects the most promising table, and extends the current partial QEP with
5790
that table. Currenly the most 'promising' table is the one with least
5791
expensive extension.\
5793
There are two extreme cases:
5794
-# When (card(remaining_tables) < search_depth), the estimate finds the
5795
best complete continuation of the partial QEP. This continuation can be
5796
used directly as a result of the search.
5797
-# When (search_depth == 1) the 'best_extension_by_limited_search'
5798
consideres the extension of the current QEP with each of the remaining
5801
All other cases are in-between these two extremes. Thus the parameter
5802
'search_depth' controlls the exhaustiveness of the search. The higher the
5803
value, the longer the optimizaton time and possibly the better the
5804
resulting plan. The lower the value, the fewer alternative plans are
5805
estimated, but the more likely to get a bad QEP.
5807
All intermediate and final results of the procedure are stored in 'join':
5808
- join->positions : modified for every partial QEP that is explored
5809
- join->best_positions: modified for the current best complete QEP
5810
- join->best_read : modified for the current best complete QEP
5811
- join->best_ref : might be partially reordered
5813
The final optimal plan is stored in 'join->best_positions', and its
5814
corresponding cost in 'join->best_read'.
5817
The following pseudocode describes the algorithm of 'greedy_search':
5820
procedure greedy_search
5821
input: remaining_tables
5826
(t, a) = best_extension(pplan, remaining_tables);
5827
pplan = concat(pplan, (t, a));
5828
remaining_tables = remaining_tables - t;
5829
} while (remaining_tables != {})
5834
where 'best_extension' is a placeholder for a procedure that selects the
5835
most "promising" of all tables in 'remaining_tables'.
5836
Currently this estimate is performed by calling
5837
'best_extension_by_limited_search' to evaluate all extensions of the
5838
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
5839
mainly depends on that of 'best_extension_by_limited_search'.
5842
If 'best_extension()' == 'best_extension_by_limited_search()', then the
5843
worst-case complexity of this algorithm is <=
5844
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
5845
complexity of greedy_search is O(N!).
5848
In the future, 'greedy_search' might be extended to support other
5849
implementations of 'best_extension', e.g. some simpler quadratic procedure.
5851
@param join pointer to the structure providing all context info
5853
@param remaining_tables set of tables not included into the partial plan yet
5854
@param search_depth controlls the exhaustiveness of the search
5855
@param prune_level the pruning heuristics that should be applied during
5865
greedy_search(JOIN *join,
5866
table_map remaining_tables,
5867
uint32_t search_depth,
5868
uint32_t prune_level)
5870
double record_count= 1.0;
5871
double read_time= 0.0;
5872
uint32_t idx= join->const_tables; // index into 'join->best_ref'
5874
uint32_t size_remain; // cardinality of remaining_tables
5876
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
5878
/* number of tables that remain to be optimized */
5879
size_remain= my_count_bits(remaining_tables);
5882
/* Find the extension of the current QEP with the lowest cost */
5883
join->best_read= DBL_MAX;
5884
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
5885
read_time, search_depth, prune_level))
5888
if (size_remain <= search_depth)
5891
'join->best_positions' contains a complete optimal extension of the
5892
current partial QEP.
5897
/* select the first table in the optimal extension as most promising */
5898
best_pos= join->best_positions[idx];
5899
best_table= best_pos.table;
5901
Each subsequent loop of 'best_extension_by_limited_search' uses
5902
'join->positions' for cost estimates, therefore we have to update its
5905
join->positions[idx]= best_pos;
5907
/* find the position of 'best_table' in 'join->best_ref' */
5909
JOIN_TAB *pos= join->best_ref[best_idx];
5910
while (pos && best_table != pos)
5911
pos= join->best_ref[++best_idx];
5912
assert((pos != NULL)); // should always find 'best_table'
5913
/* move 'best_table' at the first free position in the array of joins */
5914
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
5916
/* compute the cost of the new plan extended with 'best_table' */
5917
record_count*= join->positions[idx].records_read;
5918
read_time+= join->positions[idx].read_time;
5920
remaining_tables&= ~(best_table->table->map);
5928
Find a good, possibly optimal, query execution plan (QEP) by a possibly
5931
The procedure searches for the optimal ordering of the query tables in set
5932
'remaining_tables' of size N, and the corresponding optimal access paths to
5933
each table. The choice of a table order and an access path for each table
5934
constitutes a query execution plan (QEP) that fully specifies how to
5937
The maximal size of the found plan is controlled by the parameter
5938
'search_depth'. When search_depth == N, the resulting plan is complete and
5939
can be used directly as a QEP. If search_depth < N, the found plan consists
5940
of only some of the query tables. Such "partial" optimal plans are useful
5941
only as input to query optimization procedures, and cannot be used directly
5944
The algorithm begins with an empty partial plan stored in 'join->positions'
5945
and a set of N tables - 'remaining_tables'. Each step of the algorithm
5946
evaluates the cost of the partial plan extended by all access plans for
5947
each of the relations in 'remaining_tables', expands the current partial
5948
plan with the access plan that results in lowest cost of the expanded
5949
partial plan, and removes the corresponding relation from
5950
'remaining_tables'. The algorithm continues until it either constructs a
5951
complete optimal plan, or constructs an optimal plartial plan with size =
5954
The final optimal plan is stored in 'join->best_positions'. The
5955
corresponding cost of the optimal plan is in 'join->best_read'.
5958
The procedure uses a recursive depth-first search where the depth of the
5959
recursion (and thus the exhaustiveness of the search) is controlled by the
5960
parameter 'search_depth'.
5963
The pseudocode below describes the algorithm of
5964
'best_extension_by_limited_search'. The worst-case complexity of this
5965
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
5966
the complexity of greedy_search is O(N!).
5969
procedure best_extension_by_limited_search(
5970
pplan in, // in, partial plan of tables-joined-so-far
5971
pplan_cost, // in, cost of pplan
5972
remaining_tables, // in, set of tables not referenced in pplan
5973
best_plan_so_far, // in/out, best plan found so far
5974
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5975
search_depth) // in, maximum size of the plans being considered
5977
for each table T from remaining_tables
5979
// Calculate the cost of using table T as above
5980
cost = complex-series-of-calculations;
5982
// Add the cost to the cost so far.
5985
if (pplan_cost >= best_plan_so_far_cost)
5986
// pplan_cost already too great, stop search
5989
pplan= expand pplan by best_access_method;
5990
remaining_tables= remaining_tables - table T;
5991
if (remaining_tables is not an empty set
5995
best_extension_by_limited_search(pplan, pplan_cost,
5998
best_plan_so_far_cost,
6003
best_plan_so_far_cost= pplan_cost;
6004
best_plan_so_far= pplan;
6011
When 'best_extension_by_limited_search' is called for the first time,
6012
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
6013
The actual implementation provides a way to optionally use pruning
6014
heuristic (controlled by the parameter 'prune_level') to reduce the search
6015
space by skipping some partial plans.
6018
The parameter 'search_depth' provides control over the recursion
6019
depth, and thus the size of the resulting optimal plan.
6021
@param join pointer to the structure providing all context info
6023
@param remaining_tables set of tables not included into the partial plan yet
6024
@param idx length of the partial QEP in 'join->positions';
6025
since a depth-first search is used, also corresponds
6026
to the current depth of the search tree;
6027
also an index in the array 'join->best_ref';
6028
@param record_count estimate for the number of records returned by the
6030
@param read_time the cost of the best partial plan
6031
@param search_depth maximum depth of the recursion and thus size of the
6033
(0 < search_depth <= join->tables+1).
6034
@param prune_level pruning heuristics that should be applied during
6036
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
6045
best_extension_by_limited_search(JOIN *join,
6046
table_map remaining_tables,
6048
double record_count,
6050
uint32_t search_depth,
6051
uint32_t prune_level)
6053
Session *session= join->session;
6054
if (session->killed) // Abort
6058
'join' is a partial plan with lower cost than the best plan so far,
6059
so continue expanding it further with the tables in 'remaining_tables'.
6062
double best_record_count= DBL_MAX;
6063
double best_read_time= DBL_MAX;
6065
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
6067
table_map real_table_bit= s->table->map;
6068
if ((remaining_tables & real_table_bit) &&
6069
!(remaining_tables & s->dependent) &&
6070
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6072
double current_record_count, current_read_time;
6073
advance_sj_state(remaining_tables, s);
6076
psergey-insideout-todo:
6077
when best_access_path() detects it could do an InsideOut scan or
6078
some other scan, have it return an insideout scan and a flag that
6079
requests to "fork" this loop iteration. (Q: how does that behave
6080
when the depth is insufficient??)
6082
/* Find the best access method from 's' to the current partial plan */
6083
best_access_path(join, s, session, remaining_tables, idx,
6084
record_count, read_time);
6085
/* Compute the cost of extending the plan with 's' */
6086
current_record_count= record_count * join->positions[idx].records_read;
6087
current_read_time= read_time + join->positions[idx].read_time;
6089
/* Expand only partial plans with lower cost than the best QEP so far */
6090
if ((current_read_time +
6091
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
6093
restore_prev_nj_state(s);
6094
restore_prev_sj_state(remaining_tables, s);
6099
Prune some less promising partial plans. This heuristic may miss
6100
the optimal QEPs, thus it results in a non-exhaustive search.
6102
if (prune_level == 1)
6104
if (best_record_count > current_record_count ||
6105
best_read_time > current_read_time ||
6106
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
6108
if (best_record_count >= current_record_count &&
6109
best_read_time >= current_read_time &&
6110
/* TODO: What is the reasoning behind this condition? */
6111
(!(s->key_dependent & remaining_tables) ||
6112
join->positions[idx].records_read < 2.0))
6114
best_record_count= current_record_count;
6115
best_read_time= current_read_time;
6120
restore_prev_nj_state(s);
6121
restore_prev_sj_state(remaining_tables, s);
6126
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
6127
{ /* Recursively expand the current partial plan */
6128
std::swap(join->best_ref[idx], *pos);
6129
if (best_extension_by_limited_search(join,
6130
remaining_tables & ~real_table_bit,
6132
current_record_count,
6137
std::swap(join->best_ref[idx], *pos);
6141
'join' is either the best partial QEP with 'search_depth' relations,
6142
or the best complete QEP so far, whichever is smaller.
6144
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
6145
if (join->sort_by_table &&
6146
join->sort_by_table !=
6147
join->positions[join->const_tables].table->table)
6148
/* We have to make a temp table */
6149
current_read_time+= current_record_count;
6150
if ((search_depth == 1) || (current_read_time < join->best_read))
6152
memcpy(join->best_positions, join->positions,
6153
sizeof(POSITION) * (idx + 1));
6154
join->best_read= current_read_time - 0.001;
6157
restore_prev_nj_state(s);
6158
restore_prev_sj_state(remaining_tables, s);
6167
- TODO: this function is here only temporarily until 'greedy_search' is
6168
tested and accepted.
6175
find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count,
6178
Session *session= join->session;
6179
if (session->killed)
6183
read_time+=record_count/(double) TIME_FOR_COMPARE;
6184
if (join->sort_by_table &&
6185
join->sort_by_table !=
6186
join->positions[join->const_tables].table->table)
6187
read_time+=record_count; // We have to make a temp table
6188
if (read_time < join->best_read)
6190
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
6191
join->best_read= read_time - 0.001;
6195
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
6196
return(false); /* Found better before */
6199
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
6200
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
6202
table_map real_table_bit=s->table->map;
6203
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
6204
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6206
double records, best;
6207
advance_sj_state(rest_tables, s);
6208
best_access_path(join, s, session, rest_tables, idx, record_count,
6210
records= join->positions[idx].records_read;
6211
best= join->positions[idx].read_time;
6213
Go to the next level only if there hasn't been a better key on
6214
this level! This will cut down the search for a lot simple cases!
6216
double current_record_count=record_count*records;
6217
double current_read_time=read_time+best;
6218
if (best_record_count > current_record_count ||
6219
best_read_time > current_read_time ||
6220
(idx == join->const_tables && s->table == join->sort_by_table))
6222
if (best_record_count >= current_record_count &&
6223
best_read_time >= current_read_time &&
6224
(!(s->key_dependent & rest_tables) || records < 2.0))
6226
best_record_count=current_record_count;
6227
best_read_time=current_read_time;
6229
std::swap(join->best_ref[idx], *pos);
6230
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
6231
current_record_count,current_read_time))
6233
std::swap(join->best_ref[idx], *pos);
6235
restore_prev_nj_state(s);
6236
restore_prev_sj_state(rest_tables, s);
6237
if (join->select_options & SELECT_STRAIGHT_JOIN)
6238
break; // Don't test all combinations
6246
881
Find how much space the prevous read not const tables takes in cache.
6249
static void calc_used_field_length(Session *, JOIN_TAB *join_tab)
883
void calc_used_field_length(Session *, JoinTable *join_tab)
6251
885
uint32_t null_fields,blobs,fields,rec_length;
6252
886
Field **f_ptr,*field;
6253
MY_BITMAP *read_set= join_tab->table->read_set;;
6255
888
null_fields= blobs= fields= rec_length=0;
6256
for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++)
889
for (f_ptr=join_tab->table->getFields() ; (field= *f_ptr) ; f_ptr++)
6258
if (bitmap_is_set(read_set, field->field_index))
891
if (field->isReadSet())
6260
893
uint32_t flags=field->flags;
6262
895
rec_length+=field->pack_length();
6263
897
if (flags & BLOB_FLAG)
6265
902
if (!(flags & NOT_NULL_FLAG))
6269
909
if (null_fields)
6270
911
rec_length+=(join_tab->table->getNullFields() + 7)/8;
6271
914
if (join_tab->table->maybe_null)
6272
916
rec_length+=sizeof(bool);
6275
uint32_t blob_length=(uint) (join_tab->table->file->stats.mean_rec_length-
6276
(join_tab->table->getRecordLength()- rec_length));
6277
rec_length+=(uint) cmax((uint)4,blob_length);
6279
join_tab->used_fields=fields;
6280
join_tab->used_fieldlength=rec_length;
6281
join_tab->used_blobs=blobs;
6286
cache_record_length(JOIN *join,uint32_t idx)
6289
JOIN_TAB **pos,**end;
6290
Session *session=join->session;
6292
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
6296
JOIN_TAB *join_tab= *pos;
6297
if (!join_tab->used_fieldlength) /* Not calced yet */
6298
calc_used_field_length(session, join_tab);
6299
length+=join_tab->used_fieldlength;
6306
Get the number of different row combinations for subset of partial join
6310
join The join structure
6311
idx Number of tables in the partial join order (i.e. the
6312
partial join order is in join->positions[0..idx-1])
6313
found_ref Bitmap of tables for which we need to find # of distinct
6317
Given a partial join order (in join->positions[0..idx-1]) and a subset of
6318
tables within that join order (specified in found_ref), find out how many
6319
distinct row combinations of subset tables will be in the result of the
6322
This is used as follows: Suppose we have a table accessed with a ref-based
6323
method. The ref access depends on current rows of tables in found_ref.
6324
We want to count # of different ref accesses. We assume two ref accesses
6325
will be different if at least one of access parameters is different.
6326
Example: consider a query
6328
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
6331
t1, ref access on t1.key=c1
6332
t2, ref access on t2.key=c2
6333
t3, ref access on t3.key=t1.field
6335
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
6336
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
6337
For t3: n_ref_scans = records_read(t1)*records_read(t2)
6338
n_distinct_ref_scans = #records_read(t1)
6340
The reason for having this function (at least the latest version of it)
6341
is that we need to account for buffering in join execution.
6343
An edge-case example: if we have a non-first table in join accessed via
6344
ref(const) or ref(param) where there is a small number of different
6345
values of param, then the access will likely hit the disk cache and will
6346
not require any disk seeks.
6348
The proper solution would be to assume an LRU disk cache of some size,
6349
calculate probability of cache hits, etc. For now we just count
6350
identical ref accesses as one.
6353
Expected number of row combinations
6357
prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
6360
POSITION *pos_end= join->positions - 1;
6361
for (POSITION *pos= join->positions + idx - 1; pos != pos_end; pos--)
6363
if (pos->table->table->map & found_ref)
6365
found_ref|= pos->ref_depend_map;
6367
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
6368
with no matching row we will get position[t2].records_read==0.
6369
Actually the size of output is one null-complemented row, therefore
6370
we will use value of 1 whenever we get records_read==0.
6373
- the above case can't occur if inner part of outer join has more
6374
than one table: table with no matches will not be marked as const.
6376
- Ideally we should add 1 to records_read for every possible null-
6377
complemented row. We're not doing it because: 1. it will require
6378
non-trivial code and add overhead. 2. The value of records_read
6379
is an inprecise estimate and adding 1 (or, in the worst case,
6380
#max_nested_outer_joins=64-1) will not make it any more precise.
6382
if (pos->records_read > DBL_EPSILON)
6383
found*= pos->records_read;
921
uint32_t blob_length=(uint32_t) (join_tab->table->cursor->stats.mean_rec_length-
922
(join_tab->table->getRecordLength()- rec_length));
923
rec_length+= max((uint32_t)4,blob_length);
925
join_tab->used_fields= fields;
926
join_tab->used_fieldlength= rec_length;
927
join_tab->used_blobs= blobs;
930
StoredKey *get_store_key(Session *session,
931
optimizer::KeyUse *keyuse,
932
table_map used_tables,
933
KeyPartInfo *key_part,
934
unsigned char *key_buff,
937
Item_ref *key_use_val= static_cast<Item_ref *>(keyuse->getVal());
938
if (! ((~used_tables) & keyuse->getUsedTables())) // if const item
940
return new store_key_const_item(session,
942
key_buff + maybe_null,
943
maybe_null ? key_buff : 0,
947
else if (key_use_val->type() == Item::FIELD_ITEM ||
948
(key_use_val->type() == Item::REF_ITEM &&
949
key_use_val->ref_type() == Item_ref::OUTER_REF &&
950
(*(Item_ref**)((Item_ref*)key_use_val)->ref)->ref_type() == Item_ref::DIRECT_REF &&
951
key_use_val->real_item()->type() == Item::FIELD_ITEM))
953
return new store_key_field(session,
955
key_buff + maybe_null,
956
maybe_null ? key_buff : 0,
958
((Item_field*) key_use_val->real_item())->field,
959
key_use_val->full_name());
961
return new store_key_item(session,
963
key_buff + maybe_null,
964
maybe_null ? key_buff : 0,
6391
Set up join struct according to best position.
970
This function is only called for const items on fields which are keys.
973
returns 1 if there was some conversion made when the field was stored.
6395
get_best_combination(JOIN *join)
6398
table_map used_tables;
6399
JOIN_TAB *join_tab,*j;
6401
uint32_t table_count;
6402
Session *session=join->session;
6404
table_count=join->tables;
6405
if (!(join->join_tab=join_tab=
6406
(JOIN_TAB*) session->alloc(sizeof(JOIN_TAB)*table_count)))
6411
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
6412
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
6415
*j= *join->best_positions[tablenr].table;
6416
form=join->table[tablenr]=j->table;
6417
used_tables|= form->map;
6418
form->reginfo.join_tab=j;
6419
if (!*j->on_expr_ref)
6420
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
6421
if (j->type == JT_CONST)
6422
continue; // Handled in make_join_stat..
6427
if (j->type == JT_SYSTEM)
6429
if (j->keys.is_clear_all() || !(keyuse= join->best_positions[tablenr].key))
6432
if (tablenr != join->const_tables)
6435
else if (create_ref_for_key(join, j, keyuse, used_tables))
6436
return(true); // Something went wrong
6439
for (i=0 ; i < table_count ; i++)
6440
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
6441
update_depend_map(join);
6446
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
6447
table_map used_tables)
6449
KEYUSE *keyuse=org_keyuse;
975
bool store_val_in_field(Field *field, Item *item, enum_check_fields check_flag)
978
Table *table= field->getTable();
979
Session *session= table->in_use;
980
ha_rows cuted_fields=session->cuted_fields;
983
we should restore old value of count_cuted_fields because
984
store_val_in_field can be called from insert_query
985
with select_insert, which make count_cuted_fields= 1
987
enum_check_fields old_count_cuted_fields= session->count_cuted_fields;
988
session->count_cuted_fields= check_flag;
989
error= item->save_in_field(field, 1);
990
session->count_cuted_fields= old_count_cuted_fields;
991
return error || cuted_fields != session->cuted_fields;
994
inline void add_cond_and_fix(Item **e1, Item *e2)
998
Item* res= new Item_cond_and(*e1, e2);
1000
res->quick_fix_field();
1008
bool create_ref_for_key(Join *join,
1010
optimizer::KeyUse *org_keyuse,
1011
table_map used_tables)
1013
optimizer::KeyUse *keyuse= org_keyuse;
6450
1014
Session *session= join->session;
6451
uint32_t keyparts,length,key;
1019
KeyInfo *keyinfo= NULL;
6455
1021
/* Use best key from find_best */
6458
keyinfo=table->key_info+key;
1023
key= keyuse->getKey();
1024
keyinfo= table->key_info + key;
1027
keyparts= length= 0;
6462
1028
uint32_t found_part_ref_or_null= 0;
6464
1030
Calculate length for the used key
6849
Fill in outer join related info for the execution plan structure.
6851
For each outer join operation left after simplification of the
6852
original query the function set up the following pointers in the linear
6853
structure join->join_tab representing the selected execution plan.
6854
The first inner table t0 for the operation is set to refer to the last
6855
inner table tk through the field t0->last_inner.
6856
Any inner table ti for the operation are set to refer to the first
6857
inner table ti->first_inner.
6858
The first inner table t0 for the operation is set to refer to the
6859
first inner table of the embedding outer join operation, if there is any,
6860
through the field t0->first_upper.
6861
The on expression for the outer join operation is attached to the
6862
corresponding first inner table through the field t0->on_expr_ref.
6863
Here ti are structures of the JOIN_TAB type.
6865
EXAMPLE. For the query:
6869
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
6870
ON (t1.a=t2.a AND t1.b=t3.b)
6874
given the execution plan with the table order t1,t2,t3,t4
6875
is selected, the following references will be set;
6876
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
6877
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
6878
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
6879
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
6881
@param join reference to the info fully describing the query
6884
The function assumes that the simplification procedure has been
6885
already applied to the join query (see simplify_joins).
6886
This function can be called only after the execution plan
6891
make_outerjoin_info(JOIN *join)
6893
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6895
JOIN_TAB *tab=join->join_tab+i;
6896
Table *table=tab->table;
6897
TableList *tbl= table->pos_in_table_list;
6898
TableList *embedding= tbl->embedding;
6900
if (tbl->outer_join)
6903
Table tab is the only one inner table for outer join.
6904
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
6905
is in the query above.)
6907
tab->last_inner= tab->first_inner= tab;
6908
tab->on_expr_ref= &tbl->on_expr;
6909
tab->cond_equal= tbl->cond_equal;
6911
tab->first_upper= embedding->nested_join->first_nested;
6913
for ( ; embedding ; embedding= embedding->embedding)
6915
/* Ignore sj-nests: */
6916
if (!embedding->on_expr)
6918
nested_join_st *nested_join= embedding->nested_join;
6919
if (!nested_join->counter_)
6922
Table tab is the first inner table for nested_join.
6923
Save reference to it in the nested join structure.
6925
nested_join->first_nested= tab;
6926
tab->on_expr_ref= &embedding->on_expr;
6927
tab->cond_equal= tbl->cond_equal;
6928
if (embedding->embedding)
6929
tab->first_upper= embedding->embedding->nested_join->first_nested;
6931
if (!tab->first_inner)
6932
tab->first_inner= nested_join->first_nested;
6933
if (++nested_join->counter_ < nested_join->join_list.elements)
6935
/* Table tab is the last inner table for nested join. */
6936
nested_join->first_nested->last_inner= tab;
6944
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
6946
Session *session= join->session;
6949
add_not_null_conds(join);
6950
table_map used_tables;
6951
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
6952
{ /* there may be a select without a cond. */
6953
if (join->tables > 1)
6954
cond->update_used_tables(); // Tablenr may have changed
6955
if (join->const_tables == join->tables &&
6956
session->lex->current_select->master_unit() ==
6957
&session->lex->unit) // not upper level SELECT
6958
join->const_table_map|=RAND_TABLE_BIT;
6959
{ // Check const tables
6961
make_cond_for_table(cond,
6962
join->const_table_map,
6964
for (JOIN_TAB *tab= join->join_tab+join->const_tables;
6965
tab < join->join_tab+join->tables ; tab++)
6967
if (*tab->on_expr_ref)
6969
JOIN_TAB *cond_tab= tab->first_inner;
6970
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
6971
join->const_table_map,
6975
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
6978
tmp->quick_fix_field();
6979
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
6980
new Item_cond_and(cond_tab->select_cond,
6982
if (!cond_tab->select_cond)
6984
cond_tab->select_cond->quick_fix_field();
6987
if (const_cond && !const_cond->val_int())
6989
return(1); // Impossible const condition
6993
used_tables=((select->const_tables=join->const_table_map) |
6994
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
6995
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6997
JOIN_TAB *tab=join->join_tab+i;
6999
first_inner is the X in queries like:
7000
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
7002
JOIN_TAB *first_inner_tab= tab->first_inner;
7003
table_map current_map= tab->table->map;
7004
bool use_quick_range=0;
7008
Following force including random expression in last table condition.
7009
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
7011
if (i == join->tables-1)
7012
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
7013
used_tables|=current_map;
7015
if (tab->type == JT_REF && tab->quick &&
7016
(uint) tab->ref.key == tab->quick->index &&
7017
tab->ref.key_length < tab->quick->max_used_key_length)
7019
/* Range uses longer key; Use this instead of ref on key */
7024
tab->ref.key_parts=0; // Don't use ref key.
7025
join->best_positions[i].records_read= rows2double(tab->quick->records);
7027
We will use join cache here : prevent sorting of the first
7028
table only and sort at the end.
7030
if (i != join->const_tables && join->tables > join->const_tables + 1)
7036
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
7037
if (cond && !tmp && tab->quick)
7039
if (tab->type != JT_ALL)
7042
Don't use the quick method
7043
We come here in the case where we have 'key=constant' and
7044
the test is removed by make_cond_for_table()
7052
Hack to handle the case where we only refer to a table
7053
in the ON part of an OUTER JOIN. In this case we want the code
7054
below to check if we should use 'quick' instead.
7056
tmp= new Item_int((int64_t) 1,1); // Always true
7060
if (tmp || !cond || tab->type == JT_REF || tab->type == JT_REF_OR_NULL ||
7061
tab->type == JT_EQ_REF)
7063
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
7064
session->memdup((unsigned char*) select,
7067
return(1); // End of memory
7069
If tab is an inner table of an outer join operation,
7070
add a match guard to the pushed down predicate.
7071
The guard will turn the predicate on only after
7072
the first match for outer tables is encountered.
7077
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
7078
a cond, so neutralize the hack above.
7080
if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
7082
tab->select_cond=sel->cond=tmp;
7083
/* Push condition to storage engine if this is enabled
7084
and the condition is not guarded */
7085
tab->table->file->pushed_cond= NULL;
7086
if (session->variables.engine_condition_pushdown)
7089
make_cond_for_table(tmp, current_map, current_map, 0);
7092
/* Push condition to handler */
7093
if (!tab->table->file->cond_push(push_cond))
7094
tab->table->file->pushed_cond= push_cond;
7099
tab->select_cond= sel->cond= NULL;
7101
sel->head=tab->table;
7104
/* Use quick key read if it's a constant and it's not used
7106
if (tab->needed_reg.is_clear_all() && tab->type != JT_EQ_REF
7107
&& (tab->type != JT_REF || (uint) tab->ref.key == tab->quick->index))
7109
sel->quick=tab->quick; // Use value from get_quick_...
7110
sel->quick_keys.clear_all();
7111
sel->needed_reg.clear_all();
7119
uint32_t ref_key=(uint) sel->head->reginfo.join_tab->ref.key+1;
7120
if (i == join->const_tables && ref_key)
7122
if (!tab->const_keys.is_clear_all() &&
7123
tab->table->reginfo.impossible_range)
7126
else if (tab->type == JT_ALL && ! use_quick_range)
7128
if (!tab->const_keys.is_clear_all() &&
7129
tab->table->reginfo.impossible_range)
7130
return(1); // Impossible range
7132
We plan to scan all rows.
7133
Check again if we should use an index.
7134
We could have used an column from a previous table in
7135
the index if we are using limit and this is the first table
7138
if ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||
7139
(!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)))
7141
/* Join with outer join condition */
7142
COND *orig_cond=sel->cond;
7143
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
7146
We can't call sel->cond->fix_fields,
7147
as it will break tab->on_expr if it's AND condition
7148
(fix_fields currently removes extra AND/OR levels).
7149
Yet attributes of the just built condition are not needed.
7150
Thus we call sel->cond->quick_fix_field for safety.
7152
if (sel->cond && !sel->cond->fixed)
7153
sel->cond->quick_fix_field();
7155
if (sel->test_quick_select(session, tab->keys,
7156
used_tables & ~ current_map,
7157
(join->select_options &
7160
join->unit->select_limit_cnt), 0,
7164
Before reporting "Impossible WHERE" for the whole query
7165
we have to check isn't it only "impossible ON" instead
7167
sel->cond=orig_cond;
7168
if (!*tab->on_expr_ref ||
7169
sel->test_quick_select(session, tab->keys,
7170
used_tables & ~ current_map,
7171
(join->select_options &
7174
join->unit->select_limit_cnt),0,
7176
return(1); // Impossible WHERE
7179
sel->cond=orig_cond;
7181
/* Fix for EXPLAIN */
7183
join->best_positions[i].records_read= (double)sel->quick->records;
7187
sel->needed_reg=tab->needed_reg;
7188
sel->quick_keys.clear_all();
7190
if (!sel->quick_keys.is_subset(tab->checked_keys) ||
7191
!sel->needed_reg.is_subset(tab->checked_keys))
7193
tab->keys=sel->quick_keys;
7194
tab->keys.merge(sel->needed_reg);
7195
tab->use_quick= (!sel->needed_reg.is_clear_all() &&
7196
(select->quick_keys.is_clear_all() ||
7198
(select->quick->records >= 100L)))) ?
7200
sel->read_tables= used_tables & ~current_map;
7202
if (i != join->const_tables && tab->use_quick != 2)
7203
{ /* Read with cache */
7205
(tmp=make_cond_for_table(cond,
7206
join->const_table_map |
7210
tab->cache.select=(SQL_SELECT*)
7211
session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
7212
tab->cache.select->cond=tmp;
7213
tab->cache.select->read_tables=join->const_table_map;
7220
Push down conditions from all on expressions.
7221
Each of these conditions are guarded by a variable
7222
that turns if off just before null complemented row for
7223
outer joins is formed. Thus, the condition from an
7224
'on expression' are guaranteed not to be checked for
7225
the null complemented row.
7228
/* First push down constant conditions from on expressions */
7229
for (JOIN_TAB *join_tab= join->join_tab+join->const_tables;
7230
join_tab < join->join_tab+join->tables ; join_tab++)
7232
if (*join_tab->on_expr_ref)
7234
JOIN_TAB *cond_tab= join_tab->first_inner;
7235
COND *tmp= make_cond_for_table(*join_tab->on_expr_ref,
7236
join->const_table_map,
7240
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
7243
tmp->quick_fix_field();
7244
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
7245
new Item_cond_and(cond_tab->select_cond,tmp);
7246
if (!cond_tab->select_cond)
7248
cond_tab->select_cond->quick_fix_field();
7252
/* Push down non-constant conditions from on expressions */
7253
JOIN_TAB *last_tab= tab;
7254
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
7257
Table tab is the last inner table of an outer join.
7258
An on expression is always attached to it.
7260
COND *on_expr= *first_inner_tab->on_expr_ref;
7262
table_map used_tables2= (join->const_table_map |
7263
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7264
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
7266
current_map= tab->table->map;
7267
used_tables2|= current_map;
7268
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
7272
JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
7274
First add the guards for match variables of
7275
all embedding outer join operations.
7277
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
7282
Now add the guard turning the predicate off for
7283
the null complemented row.
7285
tmp_cond= new Item_func_trig_cond(tmp_cond,
7289
tmp_cond->quick_fix_field();
7290
/* Add the predicate to other pushed down predicates */
7291
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
7292
new Item_cond_and(cond_tab->select_cond,
7294
if (!cond_tab->select_cond)
7296
cond_tab->select_cond->quick_fix_field();
7299
first_inner_tab= first_inner_tab->first_upper;
7308
Check if given expression uses only table fields covered by the given index
7311
uses_index_fields_only()
7312
item Expression to check
7313
tbl The table having the index
7314
keyno The index number
7315
other_tbls_ok true <=> Fields of other non-const tables are allowed
7318
Check if given expression only uses fields covered by index #keyno in the
7319
table tbl. The expression can use any fields in any other tables.
7321
The expression is guaranteed not to be AND or OR - those constructs are
7322
handled outside of this function.
7329
bool uses_index_fields_only(Item *item, Table *tbl, uint32_t keyno,
7332
if (item->const_item())
7336
Don't push down the triggered conditions. Nested outer joins execution
7337
code may need to evaluate a condition several times (both triggered and
7338
untriggered), and there is no way to put thi
7339
TODO: Consider cloning the triggered condition and using the copies for:
7340
1. push the first copy down, to have most restrictive index condition
7342
2. Put the second copy into tab->select_cond.
7344
if (item->type() == Item::FUNC_ITEM &&
7345
((Item_func*)item)->functype() == Item_func::TRIG_COND_FUNC)
7348
if (!(item->used_tables() & tbl->map))
7349
return other_tbls_ok;
7351
Item::Type item_type= item->type();
7352
switch (item_type) {
7353
case Item::FUNC_ITEM:
7355
/* This is a function, apply condition recursively to arguments */
7356
Item_func *item_func= (Item_func*)item;
7358
Item **item_end= (item_func->arguments()) + item_func->argument_count();
7359
for (child= item_func->arguments(); child != item_end; child++)
7361
if (!uses_index_fields_only(*child, tbl, keyno, other_tbls_ok))
7366
case Item::COND_ITEM:
7368
/* This is a function, apply condition recursively to arguments */
7369
List_iterator<Item> li(*((Item_cond*)item)->argument_list());
7373
if (!uses_index_fields_only(item, tbl, keyno, other_tbls_ok))
7378
case Item::FIELD_ITEM:
7380
Item_field *item_field= (Item_field*)item;
7381
if (item_field->field->table != tbl)
7383
return item_field->field->part_of_key.is_set(keyno);
7385
case Item::REF_ITEM:
7386
return uses_index_fields_only(item->real_item(), tbl, keyno,
7389
return false; /* Play it safe, don't push unknown non-const items */
7394
#define ICP_COND_USES_INDEX_ONLY 10
7397
Get a part of the condition that can be checked using only index fields
7400
make_cond_for_index()
7401
cond The source condition
7402
table The table that is partially available
7403
keyno The index in the above table. Only fields covered by the index
7405
other_tbls_ok true <=> Fields of other non-const tables are allowed
7408
Get a part of the condition that can be checked when for the given table
7409
we have values only of fields covered by some index. The condition may
7410
refer to other tables, it is assumed that we have values of all of their
7414
make_cond_for_index(
7415
"cond(t1.field) AND cond(t2.key1) AND cond(t2.non_key) AND cond(t2.key2)",
7418
"cond(t1.field) AND cond(t2.key2)"
7421
Index condition, or NULL if no condition could be inferred.
7424
Item *make_cond_for_index(Item *cond, Table *table, uint32_t keyno,
7429
if (cond->type() == Item::COND_ITEM)
7431
uint32_t n_marked= 0;
7432
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7434
Item_cond_and *new_cond=new Item_cond_and;
7437
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7441
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7443
new_cond->argument_list()->push_back(fix);
7444
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7446
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7447
cond->marker= ICP_COND_USES_INDEX_ONLY;
7448
switch (new_cond->argument_list()->elements) {
7452
return new_cond->argument_list()->head();
7454
new_cond->quick_fix_field();
7460
Item_cond_or *new_cond=new Item_cond_or;
7463
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7467
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7470
new_cond->argument_list()->push_back(fix);
7471
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7473
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7474
cond->marker= ICP_COND_USES_INDEX_ONLY;
7475
new_cond->quick_fix_field();
7476
new_cond->top_level_item();
7481
if (!uses_index_fields_only(cond, table, keyno, other_tbls_ok))
7483
cond->marker= ICP_COND_USES_INDEX_ONLY;
7488
Item *make_cond_remainder(Item *cond, bool exclude_index)
7490
if (exclude_index && cond->marker == ICP_COND_USES_INDEX_ONLY)
7491
return 0; /* Already checked */
7493
if (cond->type() == Item::COND_ITEM)
7495
table_map tbl_map= 0;
7496
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7498
/* Create new top level AND item */
7499
Item_cond_and *new_cond=new Item_cond_and;
7502
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7506
Item *fix= make_cond_remainder(item, exclude_index);
7509
new_cond->argument_list()->push_back(fix);
7510
tbl_map |= fix->used_tables();
7513
switch (new_cond->argument_list()->elements) {
7517
return new_cond->argument_list()->head();
7519
new_cond->quick_fix_field();
7520
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7526
Item_cond_or *new_cond=new Item_cond_or;
7529
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7533
Item *fix= make_cond_remainder(item, false);
7536
new_cond->argument_list()->push_back(fix);
7537
tbl_map |= fix->used_tables();
7539
new_cond->quick_fix_field();
7540
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7541
new_cond->top_level_item();
7550
Try to extract and push the index condition
7554
tab A join tab that has tab->table->file and its condition
7556
keyno Index for which extract and push the condition
7557
other_tbls_ok true <=> Fields of other non-const tables are allowed
7560
Try to extract and push the index condition down to table handler
7563
static void push_index_cond(JOIN_TAB *tab, uint32_t keyno, bool other_tbls_ok)
7566
if (tab->table->file->index_flags(keyno, 0, 1) & HA_DO_INDEX_COND_PUSHDOWN &&
7567
tab->join->session->variables.engine_condition_pushdown)
7569
idx_cond= make_cond_for_index(tab->select_cond, tab->table, keyno,
7574
tab->pre_idx_push_select_cond= tab->select_cond;
7575
Item *idx_remainder_cond=
7576
tab->table->file->idx_cond_push(keyno, idx_cond);
7579
Disable eq_ref's "lookup cache" if we've pushed down an index
7581
TODO: This check happens to work on current ICP implementations, but
7582
there may exist a compliant implementation that will not work
7583
correctly with it. Sort this out when we stabilize the condition
7586
if (idx_remainder_cond != idx_cond)
7587
tab->ref.disable_cache= true;
7589
Item *row_cond= make_cond_remainder(tab->select_cond, true);
7593
if (!idx_remainder_cond)
7594
tab->select_cond= row_cond;
7597
tab->select_cond= new Item_cond_and(row_cond, idx_remainder_cond);
7598
tab->select_cond->quick_fix_field();
7599
((Item_cond_and*)tab->select_cond)->used_tables_cache=
7600
row_cond->used_tables() | idx_remainder_cond->used_tables();
7604
tab->select_cond= idx_remainder_cond;
7607
tab->select->cond= tab->select_cond;
7617
Determine if the set is already ordered for order_st BY, so it can
7618
disable join cache because it will change the ordering of the results.
7619
Code handles sort table that is at any location (not only first after
7620
the const tables) despite the fact that it's currently prohibited.
7621
We must disable join cache if the first non-const table alone is
7622
ordered. If there is a temp table the ordering is done as a last
7623
operation and doesn't prevent join cache usage.
7625
uint32_t make_join_orderinfo(JOIN *join)
7629
return join->tables;
7631
for (i=join->const_tables ; i < join->tables ; i++)
7633
JOIN_TAB *tab=join->join_tab+i;
7634
Table *table=tab->table;
7635
if ((table == join->sort_by_table &&
7636
(!join->order || join->skip_sort_order)) ||
7637
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
7647
Plan refinement stage: do various set ups for the executioner
7650
make_join_readinfo()
7651
join Join being processed
7652
options Join's options (checking for SELECT_DESCRIBE,
7653
SELECT_NO_JOIN_CACHE)
7654
no_jbuf_after Don't use join buffering after table with this number.
7657
Plan refinement stage: do various set ups for the executioner
7658
- set up use of join buffering
7659
- push index conditions
7660
- increment counters
7665
true - Out of memory
7669
make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
7672
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
7675
for (i=join->const_tables ; i < join->tables ; i++)
7677
JOIN_TAB *tab=join->join_tab+i;
7678
Table *table=tab->table;
7679
bool using_join_cache;
7680
tab->read_record.table= table;
7681
tab->read_record.file=table->file;
7682
tab->next_select=sub_select; /* normal select */
7684
TODO: don't always instruct first table's ref/range access method to
7685
produce sorted output.
7687
tab->sorted= sorted;
7688
sorted= 0; // only first must be sorted
7689
if (tab->insideout_match_tab)
7691
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
7696
switch (tab->type) {
7697
case JT_SYSTEM: // Only happens with left join
7698
table->status=STATUS_NO_RECORD;
7699
tab->read_first_record= join_read_system;
7700
tab->read_record.read_record= join_no_more_records;
7702
case JT_CONST: // Only happens with left join
7703
table->status=STATUS_NO_RECORD;
7704
tab->read_first_record= join_read_const;
7705
tab->read_record.read_record= join_no_more_records;
7706
if (table->covering_keys.is_set(tab->ref.key) &&
7710
table->file->extra(HA_EXTRA_KEYREAD);
7714
table->status=STATUS_NO_RECORD;
7717
delete tab->select->quick;
7718
tab->select->quick=0;
7722
tab->read_first_record= join_read_key;
7723
tab->read_record.read_record= join_no_more_records;
7724
if (table->covering_keys.is_set(tab->ref.key) &&
7728
table->file->extra(HA_EXTRA_KEYREAD);
7731
push_index_cond(tab, tab->ref.key, true);
7733
case JT_REF_OR_NULL:
7735
table->status=STATUS_NO_RECORD;
7738
delete tab->select->quick;
7739
tab->select->quick=0;
7743
if (table->covering_keys.is_set(tab->ref.key) &&
7747
table->file->extra(HA_EXTRA_KEYREAD);
7750
push_index_cond(tab, tab->ref.key, true);
7751
if (tab->type == JT_REF)
7753
tab->read_first_record= join_read_always_key;
7754
tab->read_record.read_record= tab->insideout_match_tab?
7755
join_read_next_same_diff : join_read_next_same;
7759
tab->read_first_record= join_read_always_key_or_null;
7760
tab->read_record.read_record= join_read_next_same_or_null;
7765
If previous table use cache
7766
If the incoming data set is already sorted don't use cache.
7768
table->status=STATUS_NO_RECORD;
7769
using_join_cache= false;
7770
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
7771
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
7772
!tab->insideout_match_tab)
7774
if ((options & SELECT_DESCRIBE) ||
7775
!join_init_cache(join->session,join->join_tab+join->const_tables,
7776
i-join->const_tables))
7778
using_join_cache= true;
7779
tab[-1].next_select=sub_select_cache; /* Patch previous */
7782
/* These init changes read_record */
7783
if (tab->use_quick == 2)
7785
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
7786
tab->read_first_record= join_init_quick_read_record;
7788
status_var_increment(join->session->status_var.select_range_check_count);
7792
tab->read_first_record= join_init_read_record;
7793
if (i == join->const_tables)
7795
if (tab->select && tab->select->quick)
7798
status_var_increment(join->session->status_var.select_range_count);
7802
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
7804
status_var_increment(join->session->status_var.select_scan_count);
7809
if (tab->select && tab->select->quick)
7812
status_var_increment(join->session->status_var.select_full_range_join_count);
7816
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
7818
status_var_increment(join->session->status_var.select_full_join_count);
7821
if (!table->no_keyread)
7823
if (tab->select && tab->select->quick &&
7824
tab->select->quick->index != MAX_KEY && //not index_merge
7825
table->covering_keys.is_set(tab->select->quick->index))
7828
table->file->extra(HA_EXTRA_KEYREAD);
7830
else if (!table->covering_keys.is_clear_all() &&
7831
!(tab->select && tab->select->quick))
7832
{ // Only read index tree
7833
if (!tab->insideout_match_tab)
7836
See bug #26447: "Using the clustered index for a table scan
7837
is always faster than using a secondary index".
7839
if (table->s->primary_key != MAX_KEY &&
7840
table->file->primary_key_is_clustered())
7841
tab->index= table->s->primary_key;
7843
tab->index= table->find_shortest_key(&table->covering_keys);
7845
tab->read_first_record= join_read_first;
7846
tab->type=JT_NEXT; // Read with index_first / index_next
7849
if (tab->select && tab->select->quick &&
7850
tab->select->quick->index != MAX_KEY && ! tab->table->key_read)
7851
push_index_cond(tab, tab->select->quick->index, !using_join_cache);
7855
break; /* purecov: deadcode */
7858
abort(); /* purecov: deadcode */
7861
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
7867
Give error if we some tables are done with a full join.
7869
This is used by multi_table_update and multi_table_delete when running
7872
@param join Join condition
7877
1 Error (full join used)
7880
bool error_if_full_join(JOIN *join)
7882
for (JOIN_TAB *tab=join->join_tab, *end=join->join_tab+join->tables;
7886
if (tab->type == JT_ALL && (!tab->select || !tab->select->quick))
7888
my_message(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE,
7889
ER(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE), MYF(0));
7901
void JOIN_TAB::cleanup()
1276
void JoinTable::cleanup()
1278
safe_delete(select);
7907
1281
if (cache.buff)
1283
size_t size= cache.end - cache.buff;
1284
global_join_buffer.sub(size);
7908
1285
free(cache.buff);
9575
propagate_cond_constants(Session *session, I_List<COND_CMP> *save_list,
9576
COND *and_father, COND *cond)
2613
static void propagate_cond_constants(Session *session,
2614
list<COND_CMP>& save_list,
9578
2618
if (cond->type() == Item::COND_ITEM)
9580
bool and_level= ((Item_cond*) cond)->functype() ==
9581
Item_func::COND_AND_FUNC;
9582
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
2620
bool and_level= ((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC;
2621
List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
9584
I_List<COND_CMP> save;
2623
list<COND_CMP> save;
9585
2624
while ((item=li++))
9587
propagate_cond_constants(session, &save,and_level ? cond : item, item);
2626
propagate_cond_constants(session, save, and_level ? cond : item, item);
9590
{ // Handle other found items
9591
I_List_iterator<COND_CMP> cond_itr(save);
9593
while ((cond_cmp=cond_itr++))
2630
// Handle other found items
2631
for (list<COND_CMP>::iterator iter= save.begin(); iter != save.end(); ++iter)
9595
Item **args= cond_cmp->cmp_func->arguments();
9596
if (!args[0]->const_item())
9597
change_cond_ref_to_const(session, &save,cond_cmp->and_level,
9598
cond_cmp->and_level, args[0], args[1]);
2633
Item **args= iter->second->arguments();
2634
if (not args[0]->const_item())
2636
change_cond_ref_to_const(session, save, iter->first,
2637
iter->first, args[0], args[1] );
9602
2642
else if (and_father != cond && !cond->marker) // In a AND group
9604
2644
if (cond->type() == Item::FUNC_ITEM &&
9605
(((Item_func*) cond)->functype() == Item_func::EQ_FUNC ||
9606
((Item_func*) cond)->functype() == Item_func::EQUAL_FUNC))
2645
(((Item_func*) cond)->functype() == Item_func::EQ_FUNC ||
2646
((Item_func*) cond)->functype() == Item_func::EQUAL_FUNC))
9608
2648
Item_func_eq *func=(Item_func_eq*) cond;
9609
2649
Item **args= func->arguments();
9610
2650
bool left_const= args[0]->const_item();
9611
2651
bool right_const= args[1]->const_item();
9612
if (!(left_const && right_const) &&
9613
args[0]->result_type() == args[1]->result_type())
2652
if (!(left_const && right_const) && args[0]->result_type() == args[1]->result_type())
9617
2656
resolve_const_item(session, &args[1], args[0]);
9618
func->update_used_tables();
2657
func->update_used_tables();
9619
2658
change_cond_ref_to_const(session, save_list, and_father, and_father,
9620
2659
args[0], args[1]);
9622
else if (left_const)
2661
else if (left_const)
9624
2663
resolve_const_item(session, &args[0], args[1]);
9625
func->update_used_tables();
2664
func->update_used_tables();
9626
2665
change_cond_ref_to_const(session, save_list, and_father, and_father,
9627
2666
args[1], args[0]);
9636
Simplify joins replacing outer joins by inner joins whenever it's
9639
The function, during a retrieval of join_list, eliminates those
9640
outer joins that can be converted into inner join, possibly nested.
9641
It also moves the on expressions for the converted outer joins
9642
and from inner joins to conds.
9643
The function also calculates some attributes for nested joins:
9647
- on_expr_dep_tables
9648
The first two attributes are used to test whether an outer join can
9649
be substituted for an inner join. The third attribute represents the
9650
relation 'to be dependent on' for tables. If table t2 is dependent
9651
on table t1, then in any evaluated execution plan table access to
9652
table t2 must precede access to table t2. This relation is used also
9653
to check whether the query contains invalid cross-references.
9654
The forth attribute is an auxiliary one and is used to calculate
9656
As the attribute dep_tables qualifies possibles orders of tables in the
9657
execution plan, the dependencies required by the straight join
9658
modifiers are reflected in this attribute as well.
9659
The function also removes all braces that can be removed from the join
9660
expression without changing its meaning.
9663
An outer join can be replaced by an inner join if the where condition
9664
or the on expression for an embedding nested join contains a conjunctive
9665
predicate rejecting null values for some attribute of the inner tables.
9669
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9671
the predicate t2.b < 5 rejects nulls.
9672
The query is converted first to:
9674
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9676
then to the equivalent form:
9678
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
9682
Similarly the following query:
9684
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
9689
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
9693
One conversion might trigger another:
9695
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
9696
LEFT JOIN t3 ON t3.b=t2.b
9697
WHERE t3 IS NOT NULL =>
9698
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
9699
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
9700
SELECT * FROM t1, t2, t3
9701
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
9704
The function removes all unnecessary braces from the expression
9705
produced by the conversions.
9708
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9710
finally is converted to:
9712
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9717
It also will remove braces from the following queries:
9719
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
9720
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
9723
The benefit of this simplification procedure is that it might return
9724
a query for which the optimizer can evaluate execution plan with more
9725
join orders. With a left join operation the optimizer does not
9726
consider any plan where one of the inner tables is before some of outer
9730
The function is implemented by a recursive procedure. On the recursive
9731
ascent all attributes are calculated, all outer joins that can be
9732
converted are replaced and then all unnecessary braces are removed.
9733
As join list contains join tables in the reverse order sequential
9734
elimination of outer joins does not require extra recursive calls.
9737
Remove all semi-joins that have are within another semi-join (i.e. have
9738
an "ancestor" semi-join nest)
9741
Here is an example of a join query with invalid cross references:
9743
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
9746
@param join reference to the query info
9747
@param join_list list representation of the join to be converted
9748
@param conds conditions to add on expressions for converted joins
9749
@param top true <=> conds is the where condition
9752
- The new condition, if success
9757
simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top,
9761
nested_join_st *nested_join;
9762
TableList *prev_table= 0;
9763
List_iterator<TableList> li(*join_list);
9766
Try to simplify join operations from join_list.
9767
The most outer join operation is checked for conversion first.
9769
while ((table= li++))
9771
table_map used_tables;
9772
table_map not_null_tables= (table_map) 0;
9774
if ((nested_join= table->nested_join))
9777
If the element of join_list is a nested join apply
9778
the procedure to its nested join list first.
9782
Item *expr= table->on_expr;
9784
If an on expression E is attached to the table,
9785
check all null rejected predicates in this expression.
9786
If such a predicate over an attribute belonging to
9787
an inner table of an embedded outer join is found,
9788
the outer join is converted to an inner join and
9789
the corresponding on expression is added to E.
9791
expr= simplify_joins(join, &nested_join->join_list,
9792
expr, false, in_sj || table->sj_on_expr);
9794
if (!table->prep_on_expr || expr != table->on_expr)
9798
table->on_expr= expr;
9799
table->prep_on_expr= expr->copy_andor_structure(join->session);
9802
nested_join->used_tables= (table_map) 0;
9803
nested_join->not_null_tables=(table_map) 0;
9804
conds= simplify_joins(join, &nested_join->join_list, conds, top,
9805
in_sj || table->sj_on_expr);
9806
used_tables= nested_join->used_tables;
9807
not_null_tables= nested_join->not_null_tables;
9811
if (!table->prep_on_expr)
9812
table->prep_on_expr= table->on_expr;
9813
used_tables= table->table->map;
9815
not_null_tables= conds->not_null_tables();
9818
if (table->embedding)
9820
table->embedding->nested_join->used_tables|= used_tables;
9821
table->embedding->nested_join->not_null_tables|= not_null_tables;
9824
if (!table->outer_join || (used_tables & not_null_tables))
9827
For some of the inner tables there are conjunctive predicates
9828
that reject nulls => the outer join can be replaced by an inner join.
9830
table->outer_join= 0;
9833
/* Add ON expression to the WHERE or upper-level ON condition. */
9836
conds= and_conds(conds, table->on_expr);
9837
conds->top_level_item();
9838
/* conds is always a new item as both cond and on_expr existed */
9839
assert(!conds->fixed);
9840
conds->fix_fields(join->session, &conds);
9843
conds= table->on_expr;
9844
table->prep_on_expr= table->on_expr= 0;
9852
Only inner tables of non-convertible outer joins
9853
remain with on_expr.
9857
table->dep_tables|= table->on_expr->used_tables();
9858
if (table->embedding)
9860
table->dep_tables&= ~table->embedding->nested_join->used_tables;
9862
Embedding table depends on tables used
9863
in embedded on expressions.
9865
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
9868
table->dep_tables&= ~table->table->map;
9873
/* The order of tables is reverse: prev_table follows table */
9874
if (prev_table->straight)
9875
prev_table->dep_tables|= used_tables;
9876
if (prev_table->on_expr)
9878
prev_table->dep_tables|= table->on_expr_dep_tables;
9879
table_map prev_used_tables= prev_table->nested_join ?
9880
prev_table->nested_join->used_tables :
9881
prev_table->table->map;
9883
If on expression contains only references to inner tables
9884
we still make the inner tables dependent on the outer tables.
9885
It would be enough to set dependency only on one outer table
9886
for them. Yet this is really a rare case.
9888
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
9889
prev_table->dep_tables|= used_tables;
9896
Flatten nested joins that can be flattened.
9897
no ON expression and not a semi-join => can be flattened.
9900
while ((table= li++))
9902
nested_join= table->nested_join;
9903
if (table->sj_on_expr && !in_sj)
9906
If this is a semi-join that is not contained within another semi-join,
9907
leave it intact (otherwise it is flattened)
9909
join->select_lex->sj_nests.push_back(table);
9911
else if (nested_join && !table->on_expr)
9914
List_iterator<TableList> it(nested_join->join_list);
9917
tbl->embedding= table->embedding;
9918
tbl->join_list= table->join_list;
9920
li.replace(nested_join->join_list);
9928
Assign each nested join structure a bit in nested_join_map.
9930
Assign each nested join structure (except "confluent" ones - those that
9931
embed only one element) a bit in nested_join_map.
9933
@param join Join being processed
9934
@param join_list List of tables
9935
@param first_unused Number of first unused bit in nested_join_map before the
9939
This function is called after simplify_joins(), when there are no
9940
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
9941
we will not run out of bits in nested_join_map.
9944
First unused bit in nested_join_map after the call.
9947
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
9948
uint32_t first_unused)
9950
List_iterator<TableList> li(*join_list);
9952
while ((table= li++))
9954
nested_join_st *nested_join;
9955
if ((nested_join= table->nested_join))
9958
It is guaranteed by simplify_joins() function that a nested join
9959
that has only one child is either
9960
- a single-table view (the child is the underlying table), or
9961
- a single-table semi-join nest
9963
We don't assign bits to such sj-nests because
9964
1. it is redundant (a "sequence" of one table cannot be interleaved
9966
2. we could run out bits in nested_join_map otherwise.
9968
if (nested_join->join_list.elements != 1)
9970
/* Don't assign bits to sj-nests */
9972
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
9973
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
9978
return(first_unused);
9983
Set nested_join_st::counter=0 in all nested joins in passed list.
9985
Recursively set nested_join_st::counter=0 for all nested joins contained in
9986
the passed join_list.
9988
@param join_list List of nested joins to process. It may also contain base
9989
tables which will be ignored.
9992
static void reset_nj_counters(List<TableList> *join_list)
9994
List_iterator<TableList> li(*join_list);
9996
while ((table= li++))
9998
nested_join_st *nested_join;
9999
if ((nested_join= table->nested_join))
10001
nested_join->counter_= 0;
10002
reset_nj_counters(&nested_join->join_list);
10010
2674
Check interleaving with an inner tables of an outer join for
10900
3539
rc= evaluate_join_record(join, join_tab, error);
10903
if (rc == NESTED_LOOP_NO_MORE_ROWS &&
10904
join_tab->last_inner && !join_tab->found)
3542
if (rc == NESTED_LOOP_NO_MORE_ROWS and join_tab->last_inner && !join_tab->found)
10905
3544
rc= evaluate_null_complemented_join_record(join, join_tab);
10907
3547
if (rc == NESTED_LOOP_NO_MORE_ROWS)
10908
3549
rc= NESTED_LOOP_OK;
10916
SemiJoinDuplicateElimination: Weed out duplicate row combinations
10919
do_sj_dups_weedout()
10923
1 The row combination is a duplicate (discard it)
10924
0 The row combination is not a duplicate (continue)
10927
int do_sj_dups_weedout(Session *session, SJ_TMP_TABLE *sjtbl)
10930
SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
10931
SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
10932
unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;
10933
unsigned char *nulls_ptr= ptr;
10935
/* Put the the rowids tuple into table->record[0]: */
10937
// 1. Store the length
10938
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
10940
*ptr= (unsigned char)(sjtbl->rowid_len + sjtbl->null_bytes);
10945
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
10949
// 2. Zero the null bytes
10950
if (sjtbl->null_bytes)
10952
memset(ptr, 0, sjtbl->null_bytes);
10953
ptr += sjtbl->null_bytes;
10956
// 3. Put the rowids
10957
for (uint32_t i=0; tab != tab_end; tab++, i++)
10959
handler *h= tab->join_tab->table->file;
10960
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
10962
/* It's a NULL-complemented row */
10963
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
10964
memset(ptr + tab->rowid_offset, 0, h->ref_length);
10968
/* Copy the rowid value */
10969
if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
10970
h->position(tab->join_tab->table->record[0]);
10971
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
10975
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
10978
/* create_myisam_from_heap will generate error if needed */
10979
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
10980
create_myisam_from_heap(session, sjtbl->tmp_table, sjtbl->start_recinfo,
10981
&sjtbl->recinfo, error, 1))
10983
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
10991
SemiJoinDuplicateElimination: Reset the temporary table
10994
int do_sj_reset(SJ_TMP_TABLE *sj_tbl)
10996
if (sj_tbl->tmp_table)
10997
return sj_tbl->tmp_table->file->ha_delete_all_rows();
11002
Process one record of the nested loop join.
11004
This function will evaluate parts of WHERE/ON clauses that are
11005
applicable to the partial record on hand and in case of success
11006
submit this record to the next level of the nested loop.
11009
static enum_nested_loop_state
11010
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
11013
bool not_used_in_distinct=join_tab->not_used_in_distinct;
11014
ha_rows found_records=join->found_records;
11015
COND *select_cond= join_tab->select_cond;
11017
if (error > 0 || (join->session->is_error())) // Fatal error
11018
return NESTED_LOOP_ERROR;
11020
return NESTED_LOOP_NO_MORE_ROWS;
11021
if (join->session->killed) // Aborted by user
11023
join->session->send_kill_message();
11024
return NESTED_LOOP_KILLED; /* purecov: inspected */
11026
if (!select_cond || select_cond->val_int())
11029
There is no select condition or the attached pushed down
11030
condition is true => a match is found.
11033
while (join_tab->first_unmatched && found)
11036
The while condition is always false if join_tab is not
11037
the last inner join table of an outer join operation.
11039
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11041
Mark that a match for current outer table is found.
11042
This activates push down conditional predicates attached
11043
to the all inner tables of the outer join.
11045
first_unmatched->found= 1;
11046
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11048
if (tab->table->reginfo.not_exists_optimize)
11049
return NESTED_LOOP_NO_MORE_ROWS;
11050
/* Check all predicates that has just been activated. */
11052
Actually all predicates non-guarded by first_unmatched->found
11053
will be re-evaluated again. It could be fixed, but, probably,
11054
it's not worth doing now.
11056
if (tab->select_cond && !tab->select_cond->val_int())
11058
/* The condition attached to table tab is false */
11059
if (tab == join_tab)
11064
Set a return point if rejected predicate is attached
11065
not to the last table of the current nest level.
11067
join->return_tab= tab;
11068
return NESTED_LOOP_OK;
11073
Check whether join_tab is not the last inner table
11074
for another embedding outer join.
11076
if ((first_unmatched= first_unmatched->first_upper) &&
11077
first_unmatched->last_inner != join_tab)
11078
first_unmatched= 0;
11079
join_tab->first_unmatched= first_unmatched;
11082
JOIN_TAB *return_tab= join->return_tab;
11083
join_tab->found_match= true;
11084
if (join_tab->check_weed_out_table)
11086
int res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table);
11088
return NESTED_LOOP_ERROR;
11090
return NESTED_LOOP_OK;
11092
else if (join_tab->do_firstmatch)
11095
We should return to the join_tab->do_firstmatch after we have
11096
enumerated all the suffixes for current prefix row combination
11098
return_tab= join_tab->do_firstmatch;
11102
It was not just a return to lower loop level when one
11103
of the newly activated predicates is evaluated as false
11104
(See above join->return_tab= tab).
11106
join->examined_rows++;
11107
join->session->row_count++;
11111
enum enum_nested_loop_state rc;
11112
/* A match from join_tab is found for the current partial join. */
11113
rc= (*join_tab->next_select)(join, join_tab+1, 0);
11114
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11116
if (return_tab < join->return_tab)
11117
join->return_tab= return_tab;
11119
if (join->return_tab < join_tab)
11120
return NESTED_LOOP_OK;
11122
Test if this was a SELECT DISTINCT query on a table that
11123
was not in the field list; In this case we can abort if
11124
we found a row, as no new rows can be added to the result.
11126
if (not_used_in_distinct && found_records != join->found_records)
11127
return NESTED_LOOP_NO_MORE_ROWS;
11130
join_tab->read_record.file->unlock_row();
11135
The condition pushed down to the table join_tab rejects all rows
11136
with the beginning coinciding with the current partial join.
11138
join->examined_rows++;
11139
join->session->row_count++;
11140
join_tab->read_record.file->unlock_row();
11142
return NESTED_LOOP_OK;
11149
Construct a NULL complimented partial join record and feed it to the next
11150
level of the nested loop. This function is used in case we have
11151
an OUTER join and no matching record was found.
11154
static enum_nested_loop_state
11155
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab)
11158
The table join_tab is the first inner table of a outer join operation
11159
and no matches has been found for the current outer row.
11161
JOIN_TAB *last_inner_tab= join_tab->last_inner;
11162
/* Cache variables for faster loop */
11164
for ( ; join_tab <= last_inner_tab ; join_tab++)
11166
/* Change the the values of guard predicate variables. */
11167
join_tab->found= 1;
11168
join_tab->not_null_compl= 0;
11169
/* The outer row is complemented by nulls for each inner tables */
11170
restore_record(join_tab->table,s->default_values); // Make empty record
11171
mark_as_null_row(join_tab->table); // For group by without error
11172
select_cond= join_tab->select_cond;
11173
/* Check all attached conditions for inner table rows. */
11174
if (select_cond && !select_cond->val_int())
11175
return NESTED_LOOP_OK;
11179
The row complemented by nulls might be the first row
11180
of embedding outer joins.
11181
If so, perform the same actions as in the code
11182
for the first regular outer join row above.
11186
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11187
if ((first_unmatched= first_unmatched->first_upper) &&
11188
first_unmatched->last_inner != join_tab)
11189
first_unmatched= 0;
11190
join_tab->first_unmatched= first_unmatched;
11191
if (!first_unmatched)
11193
first_unmatched->found= 1;
11194
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11196
if (tab->select_cond && !tab->select_cond->val_int())
11198
join->return_tab= tab;
11199
return NESTED_LOOP_OK;
11204
The row complemented by nulls satisfies all conditions
11205
attached to inner tables.
11206
Send the row complemented by nulls to be joined with the
11209
return (*join_tab->next_select)(join, join_tab+1, 0);
11213
static enum_nested_loop_state
11214
flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skip_last)
11216
enum_nested_loop_state rc= NESTED_LOOP_OK;
11220
join_tab->table->null_row= 0;
11221
if (!join_tab->cache.records)
11222
return NESTED_LOOP_OK; /* Nothing to do */
11224
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
11225
if (join_tab->use_quick == 2)
11227
if (join_tab->select->quick)
11228
{ /* Used quick select last. reset it */
11229
delete join_tab->select->quick;
11230
join_tab->select->quick=0;
11233
/* read through all records */
11234
if ((error=join_init_read_record(join_tab)))
11236
reset_cache_write(&join_tab->cache);
11237
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
11240
for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
11242
tmp->status=tmp->table->status;
11243
tmp->table->status=0;
11246
info= &join_tab->read_record;
11249
if (join->session->killed)
11251
join->session->send_kill_message();
11252
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
11254
SQL_SELECT *select=join_tab->select;
11255
if (rc == NESTED_LOOP_OK &&
11256
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
11259
reset_cache_read(&join_tab->cache);
11260
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
11262
read_cached_record(join_tab);
11263
if (!select || !select->skip_record())
11266
if (!join_tab->check_weed_out_table ||
11267
!(res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table)))
11269
rc= (join_tab->next_select)(join,join_tab+1,0);
11270
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11272
reset_cache_write(&join_tab->cache);
11277
return NESTED_LOOP_ERROR;
11281
} while (!(error=info->read_record(info)));
11284
read_cached_record(join_tab); // Restore current record
11285
reset_cache_write(&join_tab->cache);
11286
if (error > 0) // Fatal error
11287
return NESTED_LOOP_ERROR; /* purecov: inspected */
11288
for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
11289
tmp2->table->status=tmp2->status;
11290
return NESTED_LOOP_OK;
11293
int safe_index_read(JOIN_TAB *tab)
3555
int safe_index_read(JoinTable *tab)
11296
3558
Table *table= tab->table;
11297
if ((error=table->file->index_read_map(table->record[0],
3559
if ((error=table->cursor->index_read_map(table->getInsertRecord(),
11298
3560
tab->ref.key_buff,
11299
3561
make_prev_keypart_map(tab->ref.key_parts),
11300
3562
HA_READ_KEY_EXACT)))
12046
4159
return(NESTED_LOOP_OK);
12051
enum_nested_loop_state
12052
end_write(JOIN *join, JOIN_TAB *,
12053
bool end_of_records)
12055
Table *table=join->tmp_table;
12057
if (join->session->killed) // Aborted by user
12059
join->session->send_kill_message();
12060
return(NESTED_LOOP_KILLED); /* purecov: inspected */
12062
if (!end_of_records)
12064
copy_fields(&join->tmp_table_param);
12065
copy_funcs(join->tmp_table_param.items_to_copy);
12066
if (!join->having || join->having->val_int())
12069
join->found_records++;
12070
if ((error=table->file->ha_write_row(table->record[0])))
12072
if (!table->file->is_fatal_error(error, HA_CHECK_DUP))
12074
if (create_myisam_from_heap(join->session, table,
12075
join->tmp_table_param.start_recinfo,
12076
&join->tmp_table_param.recinfo,
12078
return(NESTED_LOOP_ERROR); // Not a table_is_full error
12079
table->s->uniques=0; // To ensure rows are the same
12081
if (++join->send_records >= join->tmp_table_param.end_write_records &&
12082
join->do_send_rows)
12084
if (!(join->select_options & OPTION_FOUND_ROWS))
12085
return(NESTED_LOOP_QUERY_LIMIT);
12086
join->do_send_rows=0;
12087
join->unit->select_limit_cnt = HA_POS_ERROR;
12088
return(NESTED_LOOP_OK);
12093
return(NESTED_LOOP_OK);
12097
/** Group by searching after group record and updating it if possible. */
12099
static enum_nested_loop_state
12100
end_update(JOIN *join, JOIN_TAB *,
12101
bool end_of_records)
12103
Table *table=join->tmp_table;
12107
if (end_of_records)
12108
return(NESTED_LOOP_OK);
12109
if (join->session->killed) // Aborted by user
12111
join->session->send_kill_message();
12112
return(NESTED_LOOP_KILLED); /* purecov: inspected */
12115
join->found_records++;
12116
copy_fields(&join->tmp_table_param); // Groups are copied twice.
12117
/* Make a key of group index */
12118
for (group=table->group ; group ; group=group->next)
12120
Item *item= *group->item;
12121
item->save_org_in_field(group->field);
12122
/* Store in the used key if the field was 0 */
12123
if (item->maybe_null)
12124
group->buff[-1]= (char) group->field->is_null();
12126
if (!table->file->index_read_map(table->record[1],
12127
join->tmp_table_param.group_buff,
12129
HA_READ_KEY_EXACT))
12130
{ /* Update old record */
12131
restore_record(table,record[1]);
12132
update_tmptable_sum_func(join->sum_funcs,table);
12133
if ((error=table->file->ha_update_row(table->record[1],
12134
table->record[0])))
12136
table->file->print_error(error,MYF(0)); /* purecov: inspected */
12137
return(NESTED_LOOP_ERROR); /* purecov: inspected */
12139
return(NESTED_LOOP_OK);
12143
Copy null bits from group key to table
12144
We can't copy all data as the key may have different format
12145
as the row data (for example as with VARCHAR keys)
12147
KEY_PART_INFO *key_part;
12148
for (group=table->group,key_part=table->key_info[0].key_part;
12150
group=group->next,key_part++)
12152
if (key_part->null_bit)
12153
memcpy(table->record[0]+key_part->offset, group->buff, 1);
12155
init_tmptable_sum_functions(join->sum_funcs);
12156
copy_funcs(join->tmp_table_param.items_to_copy);
12157
if ((error=table->file->ha_write_row(table->record[0])))
12159
if (create_myisam_from_heap(join->session, table,
12160
join->tmp_table_param.start_recinfo,
12161
&join->tmp_table_param.recinfo,
12163
return(NESTED_LOOP_ERROR); // Not a table_is_full error
12164
/* Change method to update rows */
12165
table->file->ha_index_init(0, 0);
12166
join->join_tab[join->tables-1].next_select=end_unique_update;
12168
join->send_records++;
12169
return(NESTED_LOOP_OK);
12173
/** Like end_update, but this is done with unique constraints instead of keys. */
12175
static enum_nested_loop_state
12176
end_unique_update(JOIN *join, JOIN_TAB *,
12177
bool end_of_records)
12179
Table *table=join->tmp_table;
12182
if (end_of_records)
12183
return(NESTED_LOOP_OK);
12184
if (join->session->killed) // Aborted by user
12186
join->session->send_kill_message();
12187
return(NESTED_LOOP_KILLED); /* purecov: inspected */
12190
init_tmptable_sum_functions(join->sum_funcs);
12191
copy_fields(&join->tmp_table_param); // Groups are copied twice.
12192
copy_funcs(join->tmp_table_param.items_to_copy);
12194
if (!(error=table->file->ha_write_row(table->record[0])))
12195
join->send_records++; // New group
12198
if ((int) table->file->get_dup_key(error) < 0)
12200
table->file->print_error(error,MYF(0)); /* purecov: inspected */
12201
return(NESTED_LOOP_ERROR); /* purecov: inspected */
12203
if (table->file->rnd_pos(table->record[1],table->file->dup_ref))
12205
table->file->print_error(error,MYF(0)); /* purecov: inspected */
12206
return(NESTED_LOOP_ERROR); /* purecov: inspected */
12208
restore_record(table,record[1]);
12209
update_tmptable_sum_func(join->sum_funcs,table);
12210
if ((error=table->file->ha_update_row(table->record[1],
12211
table->record[0])))
12213
table->file->print_error(error,MYF(0)); /* purecov: inspected */
12214
return(NESTED_LOOP_ERROR); /* purecov: inspected */
12217
return(NESTED_LOOP_OK);
12222
enum_nested_loop_state
12223
end_write_group(JOIN *join, JOIN_TAB *,
12224
bool end_of_records)
4162
enum_nested_loop_state end_write_group(Join *join, JoinTable *, bool end_of_records)
12226
4164
Table *table=join->tmp_table;
12229
if (join->session->killed)
4167
if (join->session->getKilled())
12230
4168
{ // Aborted by user
12231
4169
join->session->send_kill_message();
12232
return(NESTED_LOOP_KILLED); /* purecov: inspected */
4170
return NESTED_LOOP_KILLED;
12234
if (!join->first_record || end_of_records ||
12235
(idx=test_if_item_cache_changed(join->group_fields)) >= 0)
4173
if (!join->first_record or end_of_records or (idx=test_if_item_cache_changed(join->group_fields)) >= 0)
12237
if (join->first_record || (end_of_records && !join->group))
4175
if (join->first_record or (end_of_records && !join->group))
12239
4177
int send_group_parts= join->send_group_parts;
12240
4178
if (idx < send_group_parts)
12242
if (!join->first_record)
12244
/* No matching rows for group function */
12247
copy_sum_funcs(join->sum_funcs,
12248
join->sum_funcs_end[send_group_parts]);
12249
if (!join->having || join->having->val_int())
12251
int error= table->file->ha_write_row(table->record[0]);
12252
if (error && create_myisam_from_heap(join->session, table,
12253
join->tmp_table_param.start_recinfo,
12254
&join->tmp_table_param.recinfo,
12256
return(NESTED_LOOP_ERROR);
12258
if (join->rollup.state != ROLLUP::STATE_NONE)
12260
if (join->rollup_write_data((uint) (idx+1), table))
12261
return(NESTED_LOOP_ERROR);
12263
if (end_of_records)
12264
return(NESTED_LOOP_OK);
4180
if (!join->first_record)
4182
/* No matching rows for group function */
4186
copy_sum_funcs(join->sum_funcs, join->sum_funcs_end[send_group_parts]);
4188
if (!join->having || join->having->val_int())
4190
int error= table->cursor->insertRecord(table->getInsertRecord());
4194
my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
4195
return NESTED_LOOP_ERROR;
4199
if (join->rollup.getState() != Rollup::STATE_NONE)
4201
if (join->rollup_write_data((uint32_t) (idx+1), table))
4203
return NESTED_LOOP_ERROR;
4209
return NESTED_LOOP_OK;
12269
4215
if (end_of_records)
12270
return(NESTED_LOOP_OK);
4217
return NESTED_LOOP_OK;
12271
4219
join->first_record=1;
12272
4220
test_if_item_cache_changed(join->group_fields);
12274
4222
if (idx < (int) join->send_group_parts)
12276
4224
copy_fields(&join->tmp_table_param);
12277
copy_funcs(join->tmp_table_param.items_to_copy);
4225
if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
4227
return NESTED_LOOP_ERROR;
12278
4230
if (init_sum_functions(join->sum_funcs, join->sum_funcs_end[idx+1]))
12279
return(NESTED_LOOP_ERROR);
12280
return(NESTED_LOOP_OK);
4232
return NESTED_LOOP_ERROR;
4235
return NESTED_LOOP_OK;
12283
4239
if (update_sum_func(join->sum_funcs))
12284
return(NESTED_LOOP_ERROR);
12285
return(NESTED_LOOP_OK);
4241
return NESTED_LOOP_ERROR;
4244
return NESTED_LOOP_OK;
12289
4247
/*****************************************************************************
12290
4248
Remove calculation with tables that aren't yet read. Remove also tests
12291
4249
against fields that are read through key where the table is not a
12292
4250
outer join table.
12293
4251
We can't remove tests that are made against columns which are stored
12294
4252
in sorted order.
12295
*****************************************************************************/
12299
1 if right_item is used removable reference key on left_item
12302
static bool test_if_ref(Item_field *left_item,Item *right_item)
4254
1 if right_item used is a removable reference key on left_item
4256
****************************************************************************/
4257
bool test_if_ref(Item_field *left_item,Item *right_item)
12304
4259
Field *field=left_item->field;
12305
4260
// No need to change const test. We also have to keep tests on LEFT JOIN
12306
if (!field->table->const_table && !field->table->maybe_null)
4261
if (not field->getTable()->const_table && !field->getTable()->maybe_null)
12308
Item *ref_item=part_of_refkey(field->table,field);
4263
Item *ref_item=part_of_refkey(field->getTable(),field);
12309
4264
if (ref_item && ref_item->eq(right_item,1))
12311
4266
right_item= right_item->real_item();
12312
4267
if (right_item->type() == Item::FIELD_ITEM)
12313
return (field->eq_def(((Item_field *) right_item)->field));
4268
return (field->eq_def(((Item_field *) right_item)->field));
12314
4269
/* remove equalities injected by IN->EXISTS transformation */
12315
4270
else if (right_item->type() == Item::CACHE_ITEM)
12316
4271
return ((Item_cache *)right_item)->eq_def (field);
12317
4272
if (right_item->const_item() && !(right_item->is_null()))
12320
We can remove binary fields and numerical fields except float,
12321
as float comparison isn't 100 % secure
12322
We have to keep normal strings to be able to check for end spaces
4275
We can remove binary fields and numerical fields except float,
4276
as float comparison isn't 100 % secure
4277
We have to keep normal strings to be able to check for end spaces
12324
sergefp: the above seems to be too restrictive. Counterexample:
12325
create table t100 (v varchar(10), key(v)) default charset=latin1;
12326
insert into t100 values ('a'),('a ');
12327
explain select * from t100 where v='a';
12328
The EXPLAIN shows 'using Where'. Running the query returns both
12329
rows, so it seems there are no problems with endspace in the most
12332
if (field->binary() &&
12333
field->real_type() != DRIZZLE_TYPE_VARCHAR &&
12334
field->decimals() == 0)
12336
return !store_val_in_field(field, right_item, CHECK_FIELD_WARN);
4279
sergefp: the above seems to be too restrictive. Counterexample:
4280
create table t100 (v varchar(10), key(v)) default charset=latin1;
4281
insert into t100 values ('a'),('a ');
4282
explain select * from t100 where v='a';
4283
The EXPLAIN shows 'using Where'. Running the query returns both
4284
rows, so it seems there are no problems with endspace in the most
4287
if (field->binary() &&
4288
field->real_type() != DRIZZLE_TYPE_VARCHAR &&
4289
field->decimals() == 0)
4291
return ! store_val_in_field(field, right_item, CHECK_FIELD_WARN);
12341
return 0; // keep test
12345
@brief Replaces an expression destructively inside the expression tree of
12348
@note Because of current requirements for semijoin flattening, we do not
12349
need to recurse here, hence this function will only examine the top-level
12350
AND conditions. (see JOIN::prepare, comment above the line
12351
'if (do_materialize)'
12353
@param join The top-level query.
12354
@param old_cond The expression to be replaced.
12355
@param new_cond The expression to be substituted.
12356
@param do_fix_fields If true, Item::fix_fields(Session*, Item**) is called for
12357
the new expression.
12358
@return <code>true</code> if there was an error, <code>false</code> if
12361
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
12362
Item *new_cond, bool do_fix_fields)
12364
if (join->conds == old_cond) {
12365
join->conds= new_cond;
12367
new_cond->fix_fields(join->session, &join->conds);
12371
if (join->conds->type() == Item::COND_ITEM) {
12372
List_iterator<Item> li(*((Item_cond*)join->conds)->argument_list());
12374
while ((item= li++))
12375
if (item == old_cond)
12377
li.replace(new_cond);
12379
new_cond->fix_fields(join->session, li.ref());
15351
/** Allocate memory needed for other rollup functions. */
15353
bool JOIN::rollup_init()
15358
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
15359
rollup.state= ROLLUP::STATE_INITED;
15362
Create pointers to the different sum function groups
15363
These are updated by rollup_make_fields()
15365
tmp_table_param.group_parts= send_group_parts;
15367
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
15369
sizeof(List<Item>) +
15370
ref_pointer_array_size)
15371
* send_group_parts )))
15374
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
15375
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
15376
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
15379
Prepare space for field list for the different levels
15380
These will be filled up in rollup_make_fields()
15382
for (i= 0 ; i < send_group_parts ; i++)
15384
rollup.null_items[i]= new (session->mem_root) Item_null_result();
15385
List<Item> *rollup_fields= &rollup.fields[i];
15386
rollup_fields->empty();
15387
rollup.ref_pointer_arrays[i]= ref_array;
15388
ref_array+= all_fields.elements;
15390
for (i= 0 ; i < send_group_parts; i++)
15392
for (j=0 ; j < fields_list.elements ; j++)
15393
rollup.fields[i].push_back(rollup.null_items[i]);
15395
List_iterator<Item> it(all_fields);
15397
while ((item= it++))
15399
order_st *group_tmp;
15400
bool found_in_group= 0;
15402
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
15404
if (*group_tmp->item == item)
15406
item->maybe_null= 1;
15408
if (item->const_item())
15411
For ROLLUP queries each constant item referenced in GROUP BY list
15412
is wrapped up into an Item_func object yielding the same value
15413
as the constant item. The objects of the wrapper class are never
15414
considered as constant items and besides they inherit all
15415
properties of the Item_result_field class.
15416
This wrapping allows us to ensure writing constant items
15417
into temporary tables whenever the result of the ROLLUP
15418
operation has to be written into a temporary table, e.g. when
15419
ROLLUP is used together with DISTINCT in the SELECT list.
15420
Usually when creating temporary tables for a intermidiate
15421
result we do not include fields for constant expressions.
15423
Item* new_item= new Item_func_rollup_const(item);
15426
new_item->fix_fields(session, (Item **) 0);
15427
session->change_item_tree(it.ref(), new_item);
15428
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
15430
if (*tmp->item == item)
15431
session->change_item_tree(tmp->item, new_item);
15436
if (item->type() == Item::FUNC_ITEM && !found_in_group)
15438
bool changed= false;
15439
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
15442
We have to prevent creation of a field in a temporary table for
15443
an expression that contains GROUP BY attributes.
15444
Marking the expression item as 'with_sum_func' will ensure this.
15447
item->with_sum_func= 1;
15455
Fill up rollup structures with pointers to fields to use.
15457
Creates copies of item_sum items for each sum level.
15459
@param fields_arg List of all fields (hidden and real ones)
15460
@param sel_fields Pointer to selected fields
15461
@param func Store here a pointer to all fields
15465
In this case func is pointing to next not used element.
15470
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields,
15473
List_iterator_fast<Item> it(fields_arg);
15474
Item *first_field= sel_fields.head();
15478
Create field lists for the different levels
15480
The idea here is to have a separate field list for each rollup level to
15481
avoid all runtime checks of which columns should be NULL.
15483
The list is stored in reverse order to get sum function in such an order
15484
in func that it makes it easy to reset them with init_sum_functions()
15486
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15488
rollup.fields[0] will contain list where a,b,c is NULL
15489
rollup.fields[1] will contain list where b,c is NULL
15491
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
15493
sum_funcs_end[0] points to all sum functions
15494
sum_funcs_end[1] points to all sum functions, except grand totals
15498
for (level=0 ; level < send_group_parts ; level++)
15501
uint32_t pos= send_group_parts - level -1;
15502
bool real_fields= 0;
15504
List_iterator<Item> new_it(rollup.fields[pos]);
15505
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
15506
order_st *start_group;
15508
/* Point to first hidden field */
15509
Item **ref_array= ref_array_start + fields_arg.elements-1;
15511
/* Remember where the sum functions ends for the previous level */
15512
sum_funcs_end[pos+1]= *func;
15514
/* Find the start of the group for this level */
15515
for (i= 0, start_group= group_list ;
15517
start_group= start_group->next)
15521
while ((item= it++))
15523
if (item == first_field)
15525
real_fields= 1; // End of hidden fields
15526
ref_array= ref_array_start;
15529
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
15530
(!((Item_sum*) item)->depended_from() ||
15531
((Item_sum *)item)->depended_from() == select_lex))
15535
This is a top level summary function that must be replaced with
15536
a sum function that is reset for this level.
15538
NOTE: This code creates an object which is not that nice in a
15539
sub select. Fortunately it's not common to have rollup in
15542
item= item->copy_or_same(session);
15543
((Item_sum*) item)->make_unique();
15544
*(*func)= (Item_sum*) item;
15549
/* Check if this is something that is part of this group by */
15550
order_st *group_tmp;
15551
for (group_tmp= start_group, i= pos ;
15552
group_tmp ; group_tmp= group_tmp->next, i++)
15554
if (*group_tmp->item == item)
15557
This is an element that is used by the GROUP BY and should be
15558
set to NULL in this level
15560
Item_null_result *null_item= new (session->mem_root) Item_null_result();
15563
item->maybe_null= 1; // Value will be null sometimes
15564
null_item->result_field= item->get_tmp_table_field();
15573
(void) new_it++; // Point to next item
15574
new_it.replace(item); // Replace previous
15581
sum_funcs_end[0]= *func; // Point to last function
15586
Send all rollup levels higher than the current one to the client.
15590
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15593
@param idx Level we are on:
15594
- 0 = Total sum level
15595
- 1 = First group changed (a)
15596
- 2 = Second group changed (a,b)
15601
1 If send_data_failed()
15604
int JOIN::rollup_send_data(uint32_t idx)
15607
for (i= send_group_parts ; i-- > idx ; )
15609
/* Get reference pointers to sum functions in place */
15610
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15611
ref_pointer_array_size);
15612
if ((!having || having->val_int()))
15614
if (send_records < unit->select_limit_cnt && do_send_rows &&
15615
result->send_data(rollup.fields[i]))
15620
/* Restore ref_pointer_array */
15621
set_items_ref_array(current_ref_pointer_array);
15626
Write all rollup levels higher than the current one to a temp table.
15630
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
15633
@param idx Level we are on:
15634
- 0 = Total sum level
15635
- 1 = First group changed (a)
15636
- 2 = Second group changed (a,b)
15637
@param table reference to temp table
15642
1 if write_data_failed()
15645
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
15648
for (i= send_group_parts ; i-- > idx ; )
15650
/* Get reference pointers to sum functions in place */
15651
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15652
ref_pointer_array_size);
15653
if ((!having || having->val_int()))
15657
List_iterator_fast<Item> it(rollup.fields[i]);
15658
while ((item= it++))
15660
if (item->type() == Item::NULL_ITEM && item->is_result_field())
15661
item->save_in_result_field(1);
15663
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
15664
if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
15666
if (create_myisam_from_heap(session, table_arg,
15667
tmp_table_param.start_recinfo,
15668
&tmp_table_param.recinfo,
15674
/* Restore ref_pointer_array */
15675
set_items_ref_array(current_ref_pointer_array);
15680
clear results if there are not rows found for group
15681
(end_send_group/end_write_group)
15686
clear_tables(this);
15687
copy_fields(&tmp_table_param);
15691
Item_sum *func, **func_ptr= sum_funcs;
15692
while ((func= *(func_ptr++)))
15700
Send a description about what how the select will be done to stdout.
15703
void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
15704
bool distinct,const char *message)
15706
List<Item> field_list;
15707
List<Item> item_list;
15708
Session *session=join->session;
15709
select_result *result=join->result;
15710
Item *item_null= new Item_null();
15711
const CHARSET_INFO * const cs= system_charset_info;
15713
/* Don't log this into the slow query log */
15714
session->server_status&= ~(SERVER_QUERY_NO_INDEX_USED | SERVER_QUERY_NO_GOOD_INDEX_USED);
15715
join->unit->offset_limit_cnt= 0;
15718
NOTE: the number/types of items pushed into item_list must be in sync with
15719
EXPLAIN column types as they're "defined" in Session::send_explain_fields()
15723
item_list.push_back(new Item_int((int32_t)
15724
join->select_lex->select_number));
15725
item_list.push_back(new Item_string(join->select_lex->type,
15726
strlen(join->select_lex->type), cs));
15727
for (uint32_t i=0 ; i < 7; i++)
15728
item_list.push_back(item_null);
15729
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15730
item_list.push_back(item_null);
15732
item_list.push_back(new Item_string(message,strlen(message),cs));
15733
if (result->send_data(item_list))
15736
else if (join->select_lex == join->unit->fake_select_lex)
15739
here we assume that the query will return at least two rows, so we
15740
show "filesort" in EXPLAIN. Of course, sometimes we'll be wrong
15741
and no filesort will be actually done, but executing all selects in
15742
the UNION to provide precise EXPLAIN information will hardly be
15745
char table_name_buffer[NAME_LEN];
15748
item_list.push_back(new Item_null);
15750
item_list.push_back(new Item_string(join->select_lex->type,
15751
strlen(join->select_lex->type),
15755
SELECT_LEX *sl= join->unit->first_select();
15756
uint32_t len= 6, lastop= 0;
15757
memcpy(table_name_buffer, STRING_WITH_LEN("<union"));
15758
for (; sl && len + lastop + 5 < NAME_LEN; sl= sl->next_select())
15761
lastop= snprintf(table_name_buffer + len, NAME_LEN - len,
15762
"%u,", sl->select_number);
15764
if (sl || len + lastop >= NAME_LEN)
15766
memcpy(table_name_buffer + len, STRING_WITH_LEN("...>") + 1);
15772
table_name_buffer[len - 1]= '>'; // change ',' to '>'
15774
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15777
item_list.push_back(new Item_string(join_type_str[JT_ALL],
15778
strlen(join_type_str[JT_ALL]),
15780
/* possible_keys */
15781
item_list.push_back(item_null);
15783
item_list.push_back(item_null);
15785
item_list.push_back(item_null);
15787
item_list.push_back(item_null);
15789
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15790
item_list.push_back(item_null);
15792
item_list.push_back(item_null);
15794
if (join->unit->global_parameters->order_list.first)
15795
item_list.push_back(new Item_string("Using filesort",
15798
item_list.push_back(new Item_string("", 0, cs));
15800
if (result->send_data(item_list))
15805
table_map used_tables=0;
15806
for (uint32_t i=0 ; i < join->tables ; i++)
15808
JOIN_TAB *tab=join->join_tab+i;
15809
Table *table=tab->table;
15810
TableList *table_list= tab->table->pos_in_table_list;
15812
char buff1[512], buff2[512], buff3[512];
15813
char keylen_str_buf[64];
15814
String extra(buff, sizeof(buff),cs);
15815
char table_name_buffer[NAME_LEN];
15816
String tmp1(buff1,sizeof(buff1),cs);
15817
String tmp2(buff2,sizeof(buff2),cs);
15818
String tmp3(buff3,sizeof(buff3),cs);
15827
item_list.push_back(new Item_uint((uint32_t)
15828
join->select_lex->select_number));
15830
item_list.push_back(new Item_string(join->select_lex->type,
15831
strlen(join->select_lex->type),
15833
if (tab->type == JT_ALL && tab->select && tab->select->quick)
15835
quick_type= tab->select->quick->get_type();
15836
if ((quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) ||
15837
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
15838
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION))
15839
tab->type = JT_INDEX_MERGE;
15841
tab->type = JT_RANGE;
15844
if (table->derived_select_number)
15846
/* Derived table name generation */
15847
int len= snprintf(table_name_buffer, sizeof(table_name_buffer)-1,
15849
table->derived_select_number);
15850
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15854
TableList *real_table= table->pos_in_table_list;
15855
item_list.push_back(new Item_string(real_table->alias,
15856
strlen(real_table->alias),
15859
/* "type" column */
15860
item_list.push_back(new Item_string(join_type_str[tab->type],
15861
strlen(join_type_str[tab->type]),
15863
/* Build "possible_keys" value and add it to item_list */
15864
if (!tab->keys.is_clear_all())
15867
for (j=0 ; j < table->s->keys ; j++)
15869
if (tab->keys.is_set(j))
15873
tmp1.append(table->key_info[j].name,
15874
strlen(table->key_info[j].name),
15875
system_charset_info);
15880
item_list.push_back(new Item_string(tmp1.ptr(),tmp1.length(),cs));
15882
item_list.push_back(item_null);
15884
/* Build "key", "key_len", and "ref" values and add them to item_list */
15885
if (tab->ref.key_parts)
15887
KEY *key_info=table->key_info+ tab->ref.key;
15888
register uint32_t length;
15889
item_list.push_back(new Item_string(key_info->name,
15890
strlen(key_info->name),
15891
system_charset_info));
15892
length= int64_t2str(tab->ref.key_length, keylen_str_buf, 10) -
15894
item_list.push_back(new Item_string(keylen_str_buf, length,
15895
system_charset_info));
15896
for (store_key **ref=tab->ref.key_copy ; *ref ; ref++)
15900
tmp2.append((*ref)->name(), strlen((*ref)->name()),
15901
system_charset_info);
15903
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15905
else if (tab->type == JT_NEXT)
15907
KEY *key_info=table->key_info+ tab->index;
15908
register uint32_t length;
15909
item_list.push_back(new Item_string(key_info->name,
15910
strlen(key_info->name),cs));
15911
length= int64_t2str(key_info->key_length, keylen_str_buf, 10) -
15913
item_list.push_back(new Item_string(keylen_str_buf,
15915
system_charset_info));
15916
item_list.push_back(item_null);
15918
else if (tab->select && tab->select->quick)
15920
tab->select->quick->add_keys_and_lengths(&tmp2, &tmp3);
15921
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15922
item_list.push_back(new Item_string(tmp3.ptr(),tmp3.length(),cs));
15923
item_list.push_back(item_null);
15927
if (table_list->schema_table && table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
15929
const char *tmp_buff;
15931
if (table_list->has_db_lookup_value)
15933
f_idx= table_list->schema_table->idx_field1;
15934
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15935
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15937
if (table_list->has_table_lookup_value)
15939
if (table_list->has_db_lookup_value)
15941
f_idx= table_list->schema_table->idx_field2;
15942
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15943
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15946
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15948
item_list.push_back(item_null);
15951
item_list.push_back(item_null);
15952
item_list.push_back(item_null);
15953
item_list.push_back(item_null);
15956
/* Add "rows" field to item_list. */
15957
if (table_list->schema_table)
15960
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15961
item_list.push_back(item_null);
15963
item_list.push_back(item_null);
15967
double examined_rows;
15968
if (tab->select && tab->select->quick)
15969
examined_rows= rows2double(tab->select->quick->records);
15970
else if (tab->type == JT_NEXT || tab->type == JT_ALL)
15971
examined_rows= rows2double(tab->limit ? tab->limit :
15972
tab->table->file->records());
15974
examined_rows= join->best_positions[i].records_read;
15976
item_list.push_back(new Item_int((int64_t) (uint64_t) examined_rows,
15977
MY_INT64_NUM_DECIMAL_DIGITS));
15979
/* Add "filtered" field to item_list. */
15980
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15984
f= (float) (100.0 * join->best_positions[i].records_read /
15986
item_list.push_back(new Item_float(f, 2));
15990
/* Build "Extra" field and add it to item_list. */
15991
bool key_read=table->key_read;
15992
if ((tab->type == JT_NEXT || tab->type == JT_CONST) &&
15993
table->covering_keys.is_set(tab->index))
15995
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT &&
15996
!((QUICK_ROR_INTERSECT_SELECT*)tab->select->quick)->need_to_fetch_row)
16000
item_list.push_back(new Item_string(tab->info,strlen(tab->info),cs));
16001
else if (tab->packed_info & TAB_INFO_HAVE_VALUE)
16003
if (tab->packed_info & TAB_INFO_USING_INDEX)
16004
extra.append(STRING_WITH_LEN("; Using index"));
16005
if (tab->packed_info & TAB_INFO_USING_WHERE)
16006
extra.append(STRING_WITH_LEN("; Using where"));
16007
if (tab->packed_info & TAB_INFO_FULL_SCAN_ON_NULL)
16008
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16009
/* Skip initial "; "*/
16010
const char *str= extra.ptr();
16011
uint32_t len= extra.length();
16017
item_list.push_back(new Item_string(str, len, cs));
16021
uint32_t keyno= MAX_KEY;
16022
if (tab->ref.key_parts)
16023
keyno= tab->ref.key;
16024
else if (tab->select && tab->select->quick)
16025
keyno = tab->select->quick->index;
16027
if (keyno != MAX_KEY && keyno == table->file->pushed_idx_cond_keyno &&
16028
table->file->pushed_idx_cond)
16029
extra.append(STRING_WITH_LEN("; Using index condition"));
16031
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
16032
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
16033
quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE)
16035
extra.append(STRING_WITH_LEN("; Using "));
16036
tab->select->quick->add_info_string(&extra);
16040
if (tab->use_quick == 2)
16042
/* 4 bits per 1 hex digit + terminating '\0' */
16043
char buf[MAX_KEY / 4 + 1];
16044
extra.append(STRING_WITH_LEN("; Range checked for each "
16045
"record (index map: 0x"));
16046
extra.append(tab->keys.print(buf));
16049
else if (tab->select->cond)
16051
const COND *pushed_cond= tab->table->file->pushed_cond;
16053
if (session->variables.engine_condition_pushdown && pushed_cond)
16055
extra.append(STRING_WITH_LEN("; Using where with pushed "
16057
if (session->lex->describe & DESCRIBE_EXTENDED)
16059
extra.append(STRING_WITH_LEN(": "));
16060
((COND *)pushed_cond)->print(&extra, QT_ORDINARY);
16064
extra.append(STRING_WITH_LEN("; Using where"));
16069
if (quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
16070
extra.append(STRING_WITH_LEN("; Using index for group-by"));
16072
extra.append(STRING_WITH_LEN("; Using index"));
16074
if (table->reginfo.not_exists_optimize)
16075
extra.append(STRING_WITH_LEN("; Not exists"));
16077
if (quick_type == QUICK_SELECT_I::QS_TYPE_RANGE &&
16078
!(((QUICK_RANGE_SELECT*)(tab->select->quick))->mrr_flags &
16079
HA_MRR_USE_DEFAULT_IMPL))
16081
extra.append(STRING_WITH_LEN("; Using MRR"));
16084
if (table_list->schema_table &&
16085
table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
16087
if (!table_list->table_open_method)
16088
extra.append(STRING_WITH_LEN("; Skip_open_table"));
16089
else if (table_list->table_open_method == OPEN_FRM_ONLY)
16090
extra.append(STRING_WITH_LEN("; Open_frm_only"));
16092
extra.append(STRING_WITH_LEN("; Open_full_table"));
16093
if (table_list->has_db_lookup_value &&
16094
table_list->has_table_lookup_value)
16095
extra.append(STRING_WITH_LEN("; Scanned 0 databases"));
16096
else if (table_list->has_db_lookup_value ||
16097
table_list->has_table_lookup_value)
16098
extra.append(STRING_WITH_LEN("; Scanned 1 database"));
16100
extra.append(STRING_WITH_LEN("; Scanned all databases"));
16102
if (need_tmp_table)
16105
extra.append(STRING_WITH_LEN("; Using temporary"));
16110
extra.append(STRING_WITH_LEN("; Using filesort"));
16112
if (distinct & test_all_bits(used_tables,session->used_tables))
16113
extra.append(STRING_WITH_LEN("; Distinct"));
16115
if (tab->insideout_match_tab)
16117
extra.append(STRING_WITH_LEN("; LooseScan"));
16120
if (tab->flush_weedout_table)
16121
extra.append(STRING_WITH_LEN("; Start temporary"));
16122
else if (tab->check_weed_out_table)
16123
extra.append(STRING_WITH_LEN("; End temporary"));
16124
else if (tab->do_firstmatch)
16126
extra.append(STRING_WITH_LEN("; FirstMatch("));
16127
Table *prev_table=tab->do_firstmatch->table;
16128
if (prev_table->derived_select_number)
16130
char namebuf[NAME_LEN];
16131
/* Derived table name generation */
16132
int len= snprintf(namebuf, sizeof(namebuf)-1,
16134
prev_table->derived_select_number);
16135
extra.append(namebuf, len);
16138
extra.append(prev_table->pos_in_table_list->alias);
16139
extra.append(STRING_WITH_LEN(")"));
16142
for (uint32_t part= 0; part < tab->ref.key_parts; part++)
16144
if (tab->ref.cond_guards[part])
16146
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16151
if (i > 0 && tab[-1].next_select == sub_select_cache)
16152
extra.append(STRING_WITH_LEN("; Using join buffer"));
16154
/* Skip initial "; "*/
16155
const char *str= extra.ptr();
16156
uint32_t len= extra.length();
16162
item_list.push_back(new Item_string(str, len, cs));
16164
// For next iteration
16165
used_tables|=table->map;
16166
if (result->send_data(item_list))
16170
for (SELECT_LEX_UNIT *unit= join->select_lex->first_inner_unit();
16172
unit= unit->next_unit())
16174
if (mysql_explain_union(session, unit, result))
16181
bool mysql_explain_union(Session *session, SELECT_LEX_UNIT *unit, select_result *result)
16184
SELECT_LEX *first= unit->first_select();
16186
for (SELECT_LEX *sl= first;
16188
sl= sl->next_select())
16190
// drop UNCACHEABLE_EXPLAIN, because it is for internal usage only
16191
uint8_t uncacheable= (sl->uncacheable & ~UNCACHEABLE_EXPLAIN);
16192
sl->type= (((&session->lex->select_lex)==sl)?
16193
(sl->first_inner_unit() || sl->next_select() ?
16194
"PRIMARY" : "SIMPLE"):
16196
((sl->linkage == DERIVED_TABLE_TYPE) ?
16198
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16199
"DEPENDENT SUBQUERY":
16200
(uncacheable?"UNCACHEABLE SUBQUERY":
16202
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16204
uncacheable?"UNCACHEABLE UNION":
16206
sl->options|= SELECT_DESCRIBE;
16208
if (unit->is_union())
16210
unit->fake_select_lex->select_number= UINT_MAX; // jost for initialization
16211
unit->fake_select_lex->type= "UNION RESULT";
16212
unit->fake_select_lex->options|= SELECT_DESCRIBE;
16213
if (!(res= unit->prepare(session, result, SELECT_NO_UNLOCK | SELECT_DESCRIBE)))
16215
res|= unit->cleanup();
16219
session->lex->current_select= first;
16220
unit->set_limit(unit->global_parameters);
16221
res= mysql_select(session, &first->ref_pointer_array,
16222
(TableList*) first->table_list.first,
16223
first->with_wild, first->item_list,
16225
first->order_list.elements +
16226
first->group_list.elements,
16227
(order_st*) first->order_list.first,
16228
(order_st*) first->group_list.first,
16230
(order_st*) session->lex->proc_list.first,
16231
first->options | session->options | SELECT_DESCRIBE,
16232
result, unit, first);
16234
return(res || session->is_error());
16238
6731
static void print_table_array(Session *session, String *str, TableList **table,
16239
6732
TableList **end)
16241
(*table)->print(session, str, QT_ORDINARY);
6734
(*table)->print(session, str);
16243
6736
for (TableList **tbl= table + 1; tbl < end; tbl++)