48
46
#include <drizzled/check_stack_overrun.h>
49
47
#include <drizzled/lock.h>
50
48
#include <drizzled/item/outer_ref.h>
51
#include <drizzled/index_hint.h>
52
#include <drizzled/records.h>
53
#include <drizzled/internal/iocache.h>
54
#include <drizzled/drizzled.h>
55
#include <drizzled/plugin/storage_engine.h>
57
#include <drizzled/sql_union.h>
58
#include <drizzled/optimizer/key_field.h>
59
#include <drizzled/optimizer/position.h>
60
#include <drizzled/optimizer/sargable_param.h>
61
#include <drizzled/optimizer/key_use.h>
62
#include <drizzled/optimizer/range.h>
63
#include <drizzled/optimizer/quick_range_select.h>
64
#include <drizzled/optimizer/quick_ror_intersect_select.h>
66
#include <drizzled/filesort.h>
67
#include <drizzled/sql_lex.h>
68
#include <drizzled/session.h>
69
#include <drizzled/sort_field.h>
70
#include <drizzled/select_result.h>
72
52
using namespace std;
77
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);
54
const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
55
"MAYBE_REF","ALL","range","index",
56
"ref_or_null","unique_subquery","index_subquery",
60
struct st_sargable_param;
62
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
63
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds,
64
DYNAMIC_ARRAY *keyuse);
65
static bool update_ref_and_keys(Session *session, DYNAMIC_ARRAY *keyuse,
67
uint32_t tables, COND *conds,
68
COND_EQUAL *cond_equal,
69
table_map table_map, Select_Lex *select_lex,
70
st_sargable_param **sargables);
71
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
72
static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);
73
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
74
table_map used_tables);
75
static bool choose_plan(JOIN *join,table_map join_tables);
77
static void best_access_path(JOIN *join, JOIN_TAB *s, Session *session,
78
table_map remaining_tables, uint32_t idx,
79
double record_count, double read_time);
80
static void optimize_straight_join(JOIN *join, table_map join_tables);
81
static bool greedy_search(JOIN *join, table_map remaining_tables,
82
uint32_t depth, uint32_t prune_level);
83
static bool best_extension_by_limited_search(JOIN *join,
84
table_map remaining_tables,
85
uint32_t idx, double record_count,
86
double read_time, uint32_t depth,
87
uint32_t prune_level);
88
static uint32_t determine_search_depth(JOIN* join);
89
extern "C" int join_tab_cmp(const void* ptr1, const void* ptr2);
90
extern "C" int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
92
TODO: 'find_best' is here only temporarily until 'greedy_search' is
95
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index,
96
double record_count,double read_time);
97
static uint32_t cache_record_length(JOIN *join,uint32_t index);
98
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
99
static bool get_best_combination(JOIN *join);
100
static store_key *get_store_key(Session *session,
101
KEYUSE *keyuse, table_map used_tables,
102
KEY_PART_INFO *key_part, unsigned char *key_buff,
103
uint32_t maybe_null);
104
static bool make_simple_join(JOIN *join,Table *tmp_table);
105
static void make_outerjoin_info(JOIN *join);
106
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
107
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
108
static bool only_eq_ref_tables(JOIN *join, order_st *order, table_map tables);
109
static void update_depend_map(JOIN *join);
110
static void update_depend_map(JOIN *join, order_st *order);
111
static order_st *remove_const(JOIN *join,order_st *first_order,COND *cond,
112
bool change_list, bool *simple_order);
113
static int return_zero_rows(JOIN *join, select_result *res,TableList *tables,
114
List<Item> &fields, bool send_row,
115
uint64_t select_options, const char *info,
78
117
static COND *build_equal_items(Session *session, COND *cond,
79
118
COND_EQUAL *inherited,
80
119
List<TableList> *join_list,
81
120
COND_EQUAL **cond_equal_ref);
121
static COND* substitute_for_best_equal_field(COND *cond,
122
COND_EQUAL *cond_equal,
123
void *table_join_idx);
124
static COND *simplify_joins(JOIN *join, List<TableList> *join_list,
125
COND *conds, bool top, bool in_sj);
126
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
127
static void restore_prev_nj_state(JOIN_TAB *last);
128
static void reset_nj_counters(List<TableList> *join_list);
129
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
130
uint32_t first_unused);
133
void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);
134
static void restore_prev_sj_state(const table_map remaining_tables,
135
const JOIN_TAB *tab);
137
static COND *optimize_cond(JOIN *join, COND *conds,
138
List<TableList> *join_list,
139
Item::cond_result *cond_value);
140
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
141
static int do_select(JOIN *join,List<Item> *fields,Table *tmp_table);
143
static enum_nested_loop_state
144
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
146
static enum_nested_loop_state
147
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
148
static enum_nested_loop_state
149
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
150
static enum_nested_loop_state
151
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
152
static enum_nested_loop_state
153
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
154
static enum_nested_loop_state
155
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
156
static enum_nested_loop_state
157
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
159
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
160
static int join_read_system(JOIN_TAB *tab);
161
static int join_read_const(JOIN_TAB *tab);
162
static int join_read_key(JOIN_TAB *tab);
163
static int join_read_always_key(JOIN_TAB *tab);
164
static int join_read_last_key(JOIN_TAB *tab);
165
static int join_no_more_records(READ_RECORD *info);
166
static int join_read_next(READ_RECORD *info);
167
static int join_read_next_different(READ_RECORD *info);
168
static int join_init_quick_read_record(JOIN_TAB *tab);
169
static int test_if_quick_select(JOIN_TAB *tab);
170
static int join_init_read_record(JOIN_TAB *tab);
171
static int join_read_first(JOIN_TAB *tab);
172
static int join_read_next_same(READ_RECORD *info);
173
static int join_read_next_same_diff(READ_RECORD *info);
174
static int join_read_last(JOIN_TAB *tab);
175
static int join_read_prev_same(READ_RECORD *info);
176
static int join_read_prev(READ_RECORD *info);
177
int join_read_always_key_or_null(JOIN_TAB *tab);
178
int join_read_next_same_or_null(READ_RECORD *info);
179
static COND *make_cond_for_table(COND *cond,table_map table,
180
table_map used_table,
181
bool exclude_expensive_cond);
83
182
static Item* part_of_refkey(Table *form,Field *field);
84
static bool cmp_buffer_with_ref(JoinTable *tab);
85
static void change_cond_ref_to_const(Session *session,
86
list<COND_CMP>& save_list,
91
static bool copy_blobs(Field **ptr);
183
static bool test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,
184
ha_rows select_limit, bool no_changes,
186
static bool list_contains_unique_index(Table *table,
187
bool (*find_func) (Field *, void *), void *data);
188
static bool find_field_in_item_list (Field *field, void *data);
189
static bool find_field_in_order_list (Field *field, void *data);
190
static int create_sort_index(Session *session, JOIN *join, order_st *order,
191
ha_rows filesort_limit, ha_rows select_limit,
193
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields,
195
static int remove_dup_with_compare(Session *session, Table *entry, Field **field,
196
uint32_t offset, Item *having);
197
static int remove_dup_with_hash_index(Session *session,Table *table,
198
uint32_t field_count, Field **first_field,
199
uint32_t key_length, Item *having);
200
static int join_init_cache(Session *session,JOIN_TAB *tables,uint32_t table_count);
201
static uint32_t used_blob_length(CACHE_FIELD **ptr);
202
static bool store_record_in_cache(JOIN_CACHE *cache);
203
static void reset_cache_read(JOIN_CACHE *cache);
204
static void reset_cache_write(JOIN_CACHE *cache);
205
static void read_cached_record(JOIN_TAB *tab);
206
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
207
static order_st *create_distinct_group(Session *session, Item **ref_pointer_array,
208
order_st *order, List<Item> &fields,
209
List<Item> &all_fields,
210
bool *all_order_by_fields_used);
211
static bool test_if_subpart(order_st *a,order_st *b);
212
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
213
static void calc_group_buffer(JOIN *join,order_st *group);
214
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
215
static bool alloc_group_fields(JOIN *join,order_st *group);
216
// Create list for using with tempory table
217
static bool change_to_use_tmp_fields(Session *session, Item **ref_pointer_array,
218
List<Item> &new_list1,
219
List<Item> &new_list2,
220
uint32_t elements, List<Item> &items);
221
// Create list for using with tempory table
222
static bool change_refs_to_tmp_fields(Session *session, Item **ref_pointer_array,
223
List<Item> &new_list1,
224
List<Item> &new_list2,
225
uint32_t elements, List<Item> &items);
226
static void init_tmptable_sum_functions(Item_sum **func);
227
static void update_tmptable_sum_func(Item_sum **func,Table *tmp_table);
228
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
229
static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab);
230
static bool setup_sum_funcs(Session *session, Item_sum **func_ptr);
231
static bool init_sum_functions(Item_sum **func, Item_sum **end);
232
static bool update_sum_func(Item_sum **func);
233
void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
234
bool distinct, const char *message=NULL);
235
static Item *remove_additional_cond(Item* conds);
236
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
237
static bool test_if_ref(Item_field *left_item,Item *right_item);
238
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
239
Item *new_cond, bool fix_fields);
93
241
static bool eval_const_cond(COND *cond)
95
243
return ((Item_func*) cond)->val_int() ? true : false;
99
248
This is used to mark equalities that were made from i-th IN-equality.
100
249
We limit semi-join InsideOut optimization to handling max 64 inequalities,
418
Function to setup clauses without sum functions.
420
inline int setup_without_group(Session *session, Item **ref_pointer_array,
424
List<Item> &all_fields,
427
order_st *group, bool *hidden_group_fields)
430
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
432
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
433
res= setup_conds(session, tables, leaves, conds);
435
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
436
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
438
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
439
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
440
group, hidden_group_fields);
441
session->lex->allow_sum_func= save_allow_sum_func;
276
445
/*****************************************************************************
277
446
Check fields, find best join, do the select and output fields.
278
select_query assumes that all tables are already opened
447
mysql_select assumes that all tables are already opened
279
448
*****************************************************************************/
451
Prepare of whole select (including sub queries in future).
454
Add check of calculation of GROUP functions and fields:
455
SELECT COUNT(*)+table.col1 from table1;
463
JOIN::prepare(Item ***rref_pointer_array,
464
TableList *tables_init,
465
uint32_t wild_num, COND *conds_init, uint32_t og_num,
466
order_st *order_init, order_st *group_init,
468
order_st *proc_param_init, Select_Lex *select_lex_arg,
469
Select_Lex_Unit *unit_arg)
471
// to prevent double initialization on EXPLAIN
477
group_list= group_init;
479
proc_param= proc_param_init;
480
tables_list= tables_init;
481
select_lex= select_lex_arg;
482
select_lex->join= this;
483
join_list= &select_lex->top_join_list;
484
union_part= unit_arg->is_union();
486
session->lex->current_select->is_item_list_lookup= 1;
488
If we have already executed SELECT, then it have not sense to prevent
489
its table from update (see unique_table())
491
if (session->derived_tables_processing)
492
select_lex->exclude_from_table_unique_test= true;
494
/* Check that all tables, fields, conds and order are ok */
496
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
497
setup_tables_and_check_access(session, &select_lex->context, join_list,
498
tables_list, &select_lex->leaf_tables,
502
TableList *table_ptr;
503
for (table_ptr= select_lex->leaf_tables;
505
table_ptr= table_ptr->next_leaf)
508
if (setup_wild(session, tables_list, fields_list, &all_fields, wild_num) ||
509
select_lex->setup_ref_array(session, og_num) ||
510
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
512
setup_without_group(session, (*rref_pointer_array), tables_list,
513
select_lex->leaf_tables, fields_list,
514
all_fields, &conds, order, group_list,
515
&hidden_group_fields))
516
return(-1); /* purecov: inspected */
518
ref_pointer_array= *rref_pointer_array;
522
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
523
session->where="having clause";
524
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
525
select_lex->having_fix_field= 1;
526
bool having_fix_rc= (!having->fixed &&
527
(having->fix_fields(session, &having) ||
528
having->check_cols(1)));
529
select_lex->having_fix_field= 0;
530
if (having_fix_rc || session->is_error())
531
return(-1); /* purecov: inspected */
532
session->lex->allow_sum_func= save_allow_sum_func;
536
Item_subselect *subselect;
537
Item_in_subselect *in_subs= NULL;
539
Are we in a subquery predicate?
540
TODO: the block below will be executed for every PS execution without need.
542
if ((subselect= select_lex->master_unit()->item))
544
bool do_semijoin= !test(session->variables.optimizer_switch &
545
OPTIMIZER_SWITCH_NO_SEMIJOIN);
546
if (subselect->substype() == Item_subselect::IN_SUBS)
547
in_subs= (Item_in_subselect*)subselect;
550
Check if we're in subquery that is a candidate for flattening into a
551
semi-join (which is done done in flatten_subqueries()). The
553
1. Subquery predicate is an IN/=ANY subq predicate
554
2. Subquery is a single SELECT (not a UNION)
555
3. Subquery does not have GROUP BY or order_st BY
556
4. Subquery does not use aggregate functions or HAVING
557
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
558
6. No execution method was already chosen (by a prepared statement).
560
(*). We are not in a subquery of a single table UPDATE/DELETE that
561
doesn't have a JOIN (TODO: We should handle this at some
562
point by switching to multi-table UPDATE/DELETE)
564
(**). We're not in a confluent table-less subquery, like
568
!select_lex->master_unit()->first_select()->next_select() && // 2
569
!select_lex->group_list.elements && !order && // 3
570
!having && !select_lex->with_sum_func && // 4
571
session->session_marker && // 5
572
select_lex->outer_select()->join && // (*)
573
select_lex->master_unit()->first_select()->leaf_tables && // (**)
575
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
578
if (!in_subs->left_expr->fixed &&
579
in_subs->left_expr->fix_fields(session, &in_subs->left_expr))
584
Check that the right part of the subselect contains no more than one
585
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
587
if (subselect->substype() == Item_subselect::IN_SUBS &&
588
(select_lex->item_list.elements !=
589
((Item_in_subselect*)subselect)->left_expr->cols()))
591
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
596
/* Register the subquery for further processing */
597
select_lex->outer_select()->join->sj_subselects.append(session->mem_root, in_subs);
598
in_subs->expr_join_nest= (TableList*)session->session_marker;
602
bool do_materialize= !test(session->variables.optimizer_switch &
603
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
605
Check if the subquery predicate can be executed via materialization.
606
The required conditions are:
607
1. Subquery predicate is an IN/=ANY subq predicate
608
2. Subquery is a single SELECT (not a UNION)
609
3. Subquery is not a table-less query. In this case there is no
610
point in materializing.
611
4. Subquery predicate is a top-level predicate
612
(this implies it is not negated)
613
TODO: this is a limitation that should be lifeted once we
614
implement correct NULL semantics (WL#3830)
615
5. Subquery is non-correlated
617
This is an overly restrictive condition. It can be extended to:
618
(Subquery is non-correlated ||
619
Subquery is correlated to any query outer to IN predicate ||
620
(Subquery is correlated to the immediate outer query &&
621
Subquery !contains {GROUP BY, order_st BY [LIMIT],
622
aggregate functions) && subquery predicate is not under "NOT IN"))
623
6. No execution method was already chosen (by a prepared statement).
625
(*) The subquery must be part of a SELECT statement. The current
626
condition also excludes multi-table update statements.
628
We have to determine whether we will perform subquery materialization
629
before calling the IN=>EXISTS transformation, so that we know whether to
630
perform the whole transformation or only that part of it which wraps
631
Item_in_subselect in an Item_in_optimizer.
633
if (do_materialize &&
635
!select_lex->master_unit()->first_select()->next_select() && // 2
636
select_lex->master_unit()->first_select()->leaf_tables && // 3
637
session->lex->sql_command == SQLCOM_SELECT) // *
639
if (in_subs->is_top_level_item() && // 4
640
!in_subs->is_correlated && // 5
641
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
642
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
645
Item_subselect::trans_res trans_res;
646
if ((trans_res= subselect->select_transformer(this)) !=
647
Item_subselect::RES_OK)
649
return((trans_res == Item_subselect::RES_ERROR));
658
for (ord= order; ord; ord= ord->next)
660
Item *item= *ord->item;
661
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
662
item->split_sum_func(session, ref_pointer_array, all_fields);
666
if (having && having->with_sum_func)
667
having->split_sum_func(session, ref_pointer_array, all_fields,
669
if (select_lex->inner_sum_func_list)
671
Item_sum *end=select_lex->inner_sum_func_list;
672
Item_sum *item_sum= end;
675
item_sum= item_sum->next;
676
item_sum->split_sum_func(session, ref_pointer_array,
677
all_fields, item_sum->ref_by, false);
678
} while (item_sum != end);
681
if (select_lex->inner_refs_list.elements &&
682
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
686
Check if there are references to un-aggregated columns when computing
687
aggregate functions with implicit grouping (there is no GROUP BY).
689
MODE_ONLY_FULL_GROUP_BY is enabled here by default
691
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
693
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
694
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
698
/* Caclulate the number of groups */
700
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
705
goto err; /* purecov: inspected */
707
if (result && result->prepare(fields_list, unit_arg))
708
goto err; /* purecov: inspected */
710
/* Init join struct */
711
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
712
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
713
this->group= group_list != 0;
716
#ifdef RESTRICTED_GROUP
717
if (sum_func_count && !group_list && (func_count || field_count))
719
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
723
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
725
if (alloc_func_list())
731
return(-1); /* purecov: inspected */
736
Remove the predicates pushed down into the subquery
739
JOIN::remove_subq_pushed_predicates()
740
where IN Must be NULL
741
OUT The remaining WHERE condition, or NULL
744
Given that this join will be executed using (unique|index)_subquery,
745
without "checking NULL", remove the predicates that were pushed down
748
If the subquery compares scalar values, we can remove the condition that
749
was wrapped into trig_cond (it will be checked when needed by the subquery
752
If the subquery compares row values, we need to keep the wrapped
753
equalities in the WHERE clause: when the left (outer) tuple has both NULL
754
and non-NULL values, we'll do a full table scan and will rely on the
755
equalities corresponding to non-NULL parts of left tuple to filter out
756
non-matching records.
758
TODO: We can remove the equalities that will be guaranteed to be true by the
759
fact that subquery engine will be using index lookup. This must be done only
760
for cases where there are no conversion errors of significance, e.g. 257
761
that is searched in a byte. But this requires homogenization of the return
762
codes of all Field*::store() methods.
765
void JOIN::remove_subq_pushed_predicates(Item **where)
767
if (conds->type() == Item::FUNC_ITEM &&
768
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
769
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
770
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
771
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
772
((Item_func *)conds)->arguments()[0]))
282
781
Index lookup-based subquery: save some flags for EXPLAIN output
820
Check if the table's rowid is included in the temptable
823
sj_table_is_included()
825
join_tab The table to be checked
828
SemiJoinDuplicateElimination: check the table's rowid should be included
829
in the temptable. This is so if
831
1. The table is not embedded within some semi-join nest
832
2. The has been pulled out of a semi-join nest, or
834
3. The table is functionally dependent on some previous table
836
[4. This is also true for constant tables that can't be
837
NULL-complemented but this function is not called for such tables]
840
true - Include table's rowid
844
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
846
if (join_tab->emb_sj_nest)
849
/* Check if this table is functionally dependent on the tables that
850
are within the same outer join nest
852
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
853
if (join_tab->type == JT_EQ_REF)
855
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
857
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
859
JOIN_TAB *ref_tab= join->join_tab + idx;
860
if (embedding == ref_tab->table->pos_in_table_list->embedding)
863
/* Ok, functionally dependent */
866
/* Not functionally dependent => need to include*/
872
Setup the strategies to eliminate semi-join duplicates.
875
setup_semijoin_dups_elimination()
877
options Join options (needed to see if join buffering will be
879
no_jbuf_after Another bit of information re where join buffering will
883
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
886
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
888
2. FirstMatch (pick only the 1st matching row combination of inner tables)
889
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
890
together and picking the 1st one)
892
The join order has "duplicate-generating ranges", and every range is
893
served by one strategy or a combination of FirstMatch with with some
896
"Duplicate-generating range" is defined as a range within the join order
897
that contains all of the inner tables of a semi-join. All ranges must be
898
disjoint, if tables of several semi-joins are interleaved, then the ranges
899
are joined together, which is equivalent to converting
900
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
902
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
905
Applicability conditions are as follows:
907
DuplicateWeedout strategy
908
~~~~~~~~~~~~~~~~~~~~~~~~~
910
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
911
+------+ +=========================+ +---+
914
(1) - Prefix of OuterTables (those that participate in
915
IN-equality and/or are correlated with subquery) and outer
916
Noncorrelated Tables.
917
(2) - The handled range. The range starts with the first sj-inner
918
table, and covers all sj-inner and outer tables
919
Within the range, Inner, Outer, outer Noncorrelated tables
920
may follow in any order.
921
(3) - The suffix of outer Noncorrelated tables.
926
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
927
+------+ +==================+ +---+
930
(1) - Prefix of outer and non-correlated tables
931
(2) - The handled range, which may contain only inner and
932
non-correlated tables.
933
(3) - The suffix of outer Noncorrelated tables.
938
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
939
+--------+ +===========+ +=============+ +------+
942
(1) - Prefix that may contain any outer tables. The prefix must contain
943
all the non-trivially correlated outer tables. (non-trivially means
944
that the correlation is not just through the IN-equality).
946
(2) - Inner table for which the InsideOut scan is performed.
948
(3) - The remainder of the duplicate-generating range. It is served by
949
application of FirstMatch strategy, with the exception that
950
outer IN-correlated tables are considered to be non-correlated.
952
(4) - THe suffix of outer and outer non-correlated tables.
954
If several strategies are applicable, their relative priorities are:
959
This function walks over the join order and sets up the strategies by
960
setting appropriate members in join_tab structures.
964
true Out of memory error
968
int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
970
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
973
0 - invalid (EOF marker),
975
2 - Temptable (maybe confluent),
976
3 - Temptable with join buffering
979
uint32_t start_idx; /* Left range bound */
980
uint32_t end_idx; /* Right range bound */
982
For Temptable strategy: Bitmap of all outer and correlated tables from
983
all involved join nests.
985
table_map outer_tables;
986
} dups_ranges [MAX_TABLES];
988
TableList *emb_insideout_nest= NULL;
989
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
990
tables) whose ranges we're in */
991
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
992
table_map range_start_map= 0; /* table_map at current range start */
993
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
998
First pass: locate the duplicate-generating ranges and pick the strategies.
1000
for (i=join->const_tables ; i < join->tables ; i++)
1002
JOIN_TAB *tab=join->join_tab+i;
1003
Table *table=tab->table;
1004
cur_map |= table->map;
1006
if (tab->emb_sj_nest) // Encountered an sj-inner table
1010
dups_ranges[cur_range].start_idx= i;
1011
range_start_map= cur_map & ~table->map;
1013
Remember if this is a possible start of range that is covered by
1014
the InsideOut strategy (the reason that it is not covered could
1015
be that it overlaps with anther semi-join's range. we don't
1016
support InsideOut for joined ranges)
1018
if (join->best_positions[i].use_insideout_scan)
1019
emb_insideout_nest= tab->emb_sj_nest;
1022
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
1023
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
1025
if (tab->emb_sj_nest != emb_insideout_nest)
1028
Two different semi-joins interleave. This cannot be handled by
1031
emb_insideout_nest= NULL;
1035
if (emb_sj_map) /* We're in duplicate-generating range */
1037
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
1038
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
1039
i <= no_jbuf_after && !dealing_with_jbuf)
1042
This table uses join buffering, which makes use of FirstMatch or
1043
InsideOut strategies impossible for the current and (we assume)
1044
preceding duplicate-producing ranges.
1045
That is, for the join order:
1047
x x [ x x] x [x x x] x [x x X* x] x
1049
+-----+ +-----+ | join buffering use
1052
we'll have to remove r1 and r2 and use duplicate-elimination
1053
strategy that spans all the tables, starting from the very 1st
1056
dealing_with_jbuf= true;
1057
emb_insideout_nest= false;
1060
Absorb all preceding duplicate-eliminating ranges. Their strategies
1063
for (int prev_range= 0; prev_range < cur_range; prev_range++)
1065
dups_ranges[cur_range].outer_tables |=
1066
dups_ranges[prev_range].outer_tables;
1068
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
1069
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
1074
Check if we are at the end of duplicate-producing range. We are if
1076
1. It's an InsideOut range (which presumes all correlated tables are
1077
in the prefix), and all inner tables are in the join order prefix,
1079
2. It's a DuplicateElimination range (possibly covering several
1080
SJ-nests), and all inner, outer, and correlated tables of all
1081
sj-nests are in the join order prefix.
1083
bool end_of_range= false;
1084
if (emb_insideout_nest &&
1085
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
1087
/* Save that this range is handled with InsideOut: */
1088
dups_ranges[cur_range].strategy= 1;
1091
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
1094
This is a complete range to be handled with either DuplicateWeedout
1097
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
1099
This will hold tables from within the range that need to be put
1100
into the join buffer before we can use the FirstMatch on its tail.
1102
dups_ranges[cur_range].outer_tables= emb_outer_tables &
1109
dups_ranges[cur_range].end_idx= i+1;
1110
emb_sj_map= emb_outer_tables= 0;
1111
emb_insideout_nest= NULL;
1112
dealing_with_jbuf= false;
1113
dups_ranges[++cur_range].strategy= 0;
1118
Session *session= join->session;
1119
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
1121
Second pass: setup the chosen strategies
1123
for (int j= 0; j < cur_range; j++)
1125
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
1127
if (dups_ranges[j].strategy == 1) // InsideOut strategy
1129
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
1132
else // DuplicateWeedout strategy
1134
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
1135
table_map weed_cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
1136
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
1137
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
1138
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
1139
uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
1140
JOIN_TAB *last_outer_tab= tab - 1;
1142
Walk through the range and remember
1143
- tables that need their rowids to be put into temptable
1144
- the last outer table
1146
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1148
if (sj_table_is_included(join, tab))
1150
last_tab->join_tab= tab;
1151
last_tab->rowid_offset= jt_rowid_offset;
1152
jt_rowid_offset += tab->table->file->ref_length;
1153
if (tab->table->maybe_null)
1155
last_tab->null_byte= jt_null_bits / 8;
1156
last_tab->null_bit= jt_null_bits++;
1159
tab->table->prepare_for_position();
1160
tab->rowid_keep_flags= rowid_keep_flags;
1162
weed_cur_map |= tab->table->map;
1163
if (!tab->emb_sj_nest && bitmap_covers(weed_cur_map,
1164
dups_ranges[j].outer_tables))
1165
last_outer_tab= tab;
1168
if (jt_rowid_offset) /* Temptable has at least one rowid */
1170
SJ_TMP_TABLE *sjtbl;
1171
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
1172
if (!(sjtbl= (SJ_TMP_TABLE*)session->alloc(sizeof(SJ_TMP_TABLE))) ||
1173
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) session->alloc(tabs_size)))
1175
memcpy(sjtbl->tabs, sjtabs, tabs_size);
1176
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
1177
sjtbl->rowid_len= jt_rowid_offset;
1178
sjtbl->null_bits= jt_null_bits;
1179
sjtbl->null_bytes= (jt_null_bits + 7)/8;
1181
*next_sjtbl_ptr= sjtbl;
1182
next_sjtbl_ptr= &(sjtbl->next);
1186
create_duplicate_weedout_tmp_table(session,
1191
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
1192
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
1194
tab= last_outer_tab + 1;
1195
jump_to= last_outer_tab;
1198
/* Create the FirstMatch tail */
1199
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1201
if (tab->emb_sj_nest)
1202
tab->do_firstmatch= jump_to;
1211
static void cleanup_sj_tmp_tables(JOIN *join)
1213
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
1214
sj_tbl= sj_tbl->next)
1216
if (sj_tbl->tmp_table)
1218
sj_tbl->tmp_table->free_tmp_table(join->session);
1221
join->sj_tmp_tables= NULL;
1224
uint32_t make_join_orderinfo(JOIN *join);
1227
global select optimisation.
1230
error code saved in field 'error'
1241
// to prevent double initialization on EXPLAIN
1246
session->set_proc_info("optimizing");
1247
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
1248
unit->select_limit_cnt);
1249
/* select_limit is used to decide if we are likely to scan the whole table */
1250
select_limit= unit->select_limit_cnt;
1251
if (having || (select_options & OPTION_FOUND_ROWS))
1252
select_limit= HA_POS_ERROR;
1253
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
1254
// Ignore errors of execution if option IGNORE present
1255
if (session->lex->ignore)
1256
session->lex->current_select->no_error= 1;
1258
#ifdef HAVE_REF_TO_FIELDS // Not done yet
1259
/* Add HAVING to WHERE if possible */
1260
if (having && !group_list && !sum_func_count)
1267
else if ((conds=new Item_cond_and(conds,having)))
1270
Item_cond_and can't be fixed after creation, so we do not check
1273
conds->fix_fields(session, &conds);
1274
conds->change_ref_to_fields(session, tables_list);
1275
conds->top_level_item();
1281
/* Convert all outer joins to inner joins if possible */
1282
conds= simplify_joins(this, join_list, conds, true, false);
1283
build_bitmap_for_nested_joins(join_list, 0);
1285
conds= optimize_cond(this, conds, join_list, &cond_value);
1286
if (session->is_error())
1293
having= optimize_cond(this, having, join_list, &having_value);
1294
if (session->is_error())
1299
if (select_lex->where)
1300
select_lex->cond_value= cond_value;
1301
if (select_lex->having)
1302
select_lex->having_value= having_value;
1304
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
1305
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
1306
{ /* Impossible cond */
1307
zero_result_cause= having_value == Item::COND_FALSE ?
1308
"Impossible HAVING" : "Impossible WHERE";
1314
/* Optimize count(*), cmin() and cmax() */
1315
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
1319
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
1320
to the WHERE conditions,
1321
or 1 if all items were resolved,
1322
or 0, or an error number HA_ERR_...
1324
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
1326
if (res == HA_ERR_KEY_NOT_FOUND)
1328
zero_result_cause= "No matching min/max row";
1339
zero_result_cause= "No matching min/max row";
1343
zero_result_cause= "Select tables optimized away";
1344
tables_list= 0; // All tables resolved
1346
Extract all table-independent conditions and replace the WHERE
1347
clause with them. All other conditions were computed by opt_sum_query
1348
and the MIN/MAX/COUNT function(s) have been replaced by constants,
1349
so there is no need to compute the whole WHERE clause again.
1350
Notice that make_cond_for_table() will always succeed to remove all
1351
computed conditions, because opt_sum_query() is applicable only to
1353
Preserve conditions for EXPLAIN.
1355
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
1357
COND *table_independent_conds=
1358
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
1359
conds= table_independent_conds;
1368
error= -1; // Error is sent to client
1369
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
1371
/* Calculate how to do the join */
1372
session->set_proc_info("statistics");
1373
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
1374
session->is_fatal_error)
1379
/* Remove distinct if only const tables */
1380
select_distinct= select_distinct && (const_tables != tables);
1381
session->set_proc_info("preparing");
1382
if (result->initialize_tables(this))
1384
return(1); // error == -1
1386
if (const_table_map != found_const_table_map &&
1387
!(select_options & SELECT_DESCRIBE) &&
1389
!(conds->used_tables() & RAND_TABLE_BIT) ||
1390
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
1392
zero_result_cause= "no matching row in const table";
1396
if (!(session->options & OPTION_BIG_SELECTS) &&
1397
best_read > (double) session->variables.max_join_size &&
1398
!(select_options & SELECT_DESCRIBE))
1399
{ /* purecov: inspected */
1400
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
1404
if (const_tables && !session->locked_tables &&
1405
!(select_options & SELECT_NO_UNLOCK))
1406
mysql_unlock_some_tables(session, table, const_tables);
1407
if (!conds && outer_join)
1409
/* Handle the case where we have an OUTER JOIN without a WHERE */
1410
conds=new Item_int((int64_t) 1,1); // Always true
1412
select= make_select(*table, const_table_map,
1413
const_table_map, conds, 1, &error);
1415
{ /* purecov: inspected */
1416
error= -1; /* purecov: inspected */
1420
reset_nj_counters(join_list);
1421
make_outerjoin_info(this);
1424
Among the equal fields belonging to the same multiple equality
1425
choose the one that is to be retrieved first and substitute
1426
all references to these in where condition for a reference for
1431
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
1432
conds->update_used_tables();
1436
Permorm the the optimization on fields evaluation mentioned above
1437
for all on expressions.
1439
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
1441
if (*tab->on_expr_ref)
1443
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
1446
(*tab->on_expr_ref)->update_used_tables();
1450
if (conds &&!outer_join && const_table_map != found_const_table_map &&
1451
(select_options & SELECT_DESCRIBE) &&
1452
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
1454
conds=new Item_int((int64_t) 0,1); // Always false
1456
if (make_join_select(this, select, conds))
1459
"Impossible WHERE noticed after reading const tables";
1460
return(0); // error == 0
1463
error= -1; /* if goto err */
1465
/* Optimize distinct away if possible */
1467
order_st *org_order= order;
1468
order=remove_const(this, order,conds,1, &simple_order);
1469
if (session->is_error())
1476
If we are using order_st BY NULL or order_st BY const_expression,
1477
return result in any order (even if we are using a GROUP BY)
1479
if (!order && org_order)
1483
Check if we can optimize away GROUP BY/DISTINCT.
1484
We can do that if there are no aggregate functions, the
1485
fields in DISTINCT clause (if present) and/or columns in GROUP BY
1486
(if present) contain direct references to all key parts of
1487
an unique index (in whatever order) and if the key parts of the
1488
unique index cannot contain NULLs.
1489
Note that the unique keys for DISTINCT and GROUP BY should not
1490
be the same (as long as they are unique).
1492
The FROM clause must contain a single non-constant table.
1494
if (tables - const_tables == 1 && (group_list || select_distinct) &&
1495
!tmp_table_param.sum_func_count &&
1496
(!join_tab[const_tables].select ||
1497
!join_tab[const_tables].select->quick ||
1498
join_tab[const_tables].select->quick->get_type() !=
1499
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
1502
list_contains_unique_index(join_tab[const_tables].table,
1503
find_field_in_order_list,
1504
(void *) group_list))
1507
We have found that grouping can be removed since groups correspond to
1508
only one row anyway, but we still have to guarantee correct result
1509
order. The line below effectively rewrites the query from GROUP BY
1510
<fields> to order_st BY <fields>. There are two exceptions:
1511
- if skip_sort_order is set (see above), then we can simply skip
1513
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
1514
with the GROUP BY ones, i.e. either one is a prefix of another.
1515
We only check if the order_st BY is a prefix of GROUP BY. In this case
1516
test_if_subpart() copies the ASC/DESC attributes from the original
1518
If GROUP BY is a prefix of order_st BY, then it is safe to leave
1521
if (!order || test_if_subpart(group_list, order))
1522
order= skip_sort_order ? 0 : group_list;
1524
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
1525
rewritten to IGNORE INDEX FOR order_st BY(fields).
1527
join_tab->table->keys_in_use_for_order_by=
1528
join_tab->table->keys_in_use_for_group_by;
1532
if (select_distinct &&
1533
list_contains_unique_index(join_tab[const_tables].table,
1534
find_field_in_item_list,
1535
(void *) &fields_list))
1540
if (group_list || tmp_table_param.sum_func_count)
1542
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
1545
else if (select_distinct && tables - const_tables == 1)
1548
We are only using one table. In this case we change DISTINCT to a
1550
- The GROUP BY can be done through indexes (no sort) and the order_st
1551
BY only uses selected fields.
1552
(In this case we can later optimize away GROUP BY and order_st BY)
1553
- We are scanning the whole table without LIMIT
1555
- We are using CALC_FOUND_ROWS
1556
- We are using an order_st BY that can't be optimized away.
1558
We don't want to use this optimization when we are using LIMIT
1559
because in this case we can just create a temporary table that
1560
holds LIMIT rows and stop when this table is full.
1562
JOIN_TAB *tab= &join_tab[const_tables];
1563
bool all_order_fields_used;
1565
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
1566
&tab->table->keys_in_use_for_order_by);
1567
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
1568
order, fields_list, all_fields,
1569
&all_order_fields_used)))
1571
bool skip_group= (skip_sort_order &&
1572
test_if_skip_sort_order(tab, group_list, select_limit, 1,
1573
&tab->table->keys_in_use_for_group_by) != 0);
1574
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
1575
if ((skip_group && all_order_fields_used) ||
1576
select_limit == HA_POS_ERROR ||
1577
(order && !skip_sort_order))
1579
/* Change DISTINCT to GROUP BY */
1582
if (all_order_fields_used)
1584
if (order && skip_sort_order)
1587
Force MySQL to read the table in sorted order to get result in
1590
tmp_table_param.quick_group=0;
1594
group=1; // For end_write_group
1599
else if (session->is_fatal_error) // End of memory
1604
order_st *old_group_list;
1605
group_list= remove_const(this, (old_group_list= group_list), conds,
1606
rollup.state == ROLLUP::STATE_NONE,
1608
if (session->is_error())
1613
if (old_group_list && !group_list)
1616
if (!group_list && group)
1618
order=0; // The output has only one row
1620
select_distinct= 0; // No need in distinct for 1 row
1621
group_optimized_away= 1;
1624
calc_group_buffer(this, group_list);
1625
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
1627
if (test_if_subpart(group_list, order) ||
1628
(!group_list && tmp_table_param.sum_func_count))
1631
// Can't use sort on head table if using row cache
1641
Check if we need to create a temporary table.
1642
This has to be done if all tables are not already read (const tables)
1643
and one of the following conditions holds:
1644
- We are using DISTINCT (simple distinct's are already optimized away)
1645
- We are using an order_st BY or GROUP BY on fields not in the first table
1646
- We are using different order_st BY and GROUP BY orders
1647
- The user wants us to buffer the result.
1649
need_tmp= (const_tables != tables &&
1650
((select_distinct || !simple_order || !simple_group) ||
1651
(group_list && order) ||
1652
test(select_options & OPTION_BUFFER_RESULT)));
1654
uint32_t no_jbuf_after= make_join_orderinfo(this);
1655
uint64_t select_opts_for_readinfo=
1656
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
1658
sj_tmp_tables= NULL;
1659
if (!select_lex->sj_nests.is_empty())
1660
setup_semijoin_dups_elimination(this, select_opts_for_readinfo,
1663
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1664
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1667
/* Create all structures needed for materialized subquery execution. */
1668
if (setup_subquery_materialization())
1672
is this simple IN subquery?
1674
if (!group_list && !order &&
1675
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1676
tables == 1 && conds &&
1682
if (join_tab[0].type == JT_EQ_REF &&
1683
join_tab[0].ref.items[0]->name == in_left_expr_name)
1685
remove_subq_pushed_predicates(&where);
1686
save_index_subquery_explain_info(join_tab, where);
1687
join_tab[0].type= JT_UNIQUE_SUBQUERY;
1691
subselect_uniquesubquery_engine(session,
1696
else if (join_tab[0].type == JT_REF &&
1697
join_tab[0].ref.items[0]->name == in_left_expr_name)
1699
remove_subq_pushed_predicates(&where);
1700
save_index_subquery_explain_info(join_tab, where);
1701
join_tab[0].type= JT_INDEX_SUBQUERY;
1705
subselect_indexsubquery_engine(session,
1712
} else if (join_tab[0].type == JT_REF_OR_NULL &&
1713
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1714
having->name == in_having_cond)
1716
join_tab[0].type= JT_INDEX_SUBQUERY;
1718
conds= remove_additional_cond(conds);
1719
save_index_subquery_explain_info(join_tab, conds);
1721
change_engine(new subselect_indexsubquery_engine(session,
1731
Need to tell handlers that to play it safe, it should fetch all
1732
columns of the primary key of the tables: this is because MySQL may
1733
build row pointers for the rows, and for all columns of the primary key
1734
the read set has not necessarily been set by the server code.
1736
if (need_tmp || select_distinct || group_list || order)
1738
for (uint32_t i = const_tables; i < tables; i++)
1739
join_tab[i].table->prepare_for_position();
1742
if (const_tables != tables)
1745
Because filesort always does a full table scan or a quick range scan
1746
we must add the removed reference to the select for the table.
1747
We only need to do this when we have a simple_order or simple_group
1748
as in other cases the join is done before the sort.
1750
if ((order || group_list) &&
1751
(join_tab[const_tables].type != JT_ALL) &&
1752
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
1753
((order && simple_order) || (group_list && simple_group)))
1755
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
1760
if (!(select_options & SELECT_BIG_RESULT) &&
1763
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1764
unit->select_limit_cnt, 0,
1765
&join_tab[const_tables].table->
1766
keys_in_use_for_group_by))) ||
1768
tmp_table_param.quick_group)
1770
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1775
Force using of tmp table if sorting by a SP or UDF function due to
1776
their expensive and probably non-deterministic nature.
1778
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1780
Item *item= *tmp_order->item;
1781
if (item->is_expensive())
1783
/* Force tmp table without sort */
1784
need_tmp=1; simple_order=simple_group=0;
1792
if (select_options & SELECT_DESCRIBE)
1800
The loose index scan access method guarantees that all grouping or
1801
duplicate row elimination (for distinct) is already performed
1802
during data retrieval, and that all MIN/MAX functions are already
1803
computed for each group. Thus all MIN/MAX functions should be
1804
treated as regular functions, and there is no need to perform
1805
grouping in the main execution loop.
1806
Notice that currently loose index scan is applicable only for
1807
single table queries, thus it is sufficient to test only the first
1808
join_tab element of the plan for its access method.
1810
if (join_tab->is_using_loose_index_scan())
1811
tmp_table_param.precomputed_group_by= true;
1813
/* Create a tmp table if distinct or if the sort is too complicated */
1816
session->set_proc_info("Creating tmp table");
1818
init_items_ref_array();
1820
tmp_table_param.hidden_field_count= (all_fields.elements -
1821
fields_list.elements);
1822
order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1825
Pushing LIMIT to the temporary table creation is not applicable
1826
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1827
there are aggregate functions, because in all these cases we need
1830
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1832
!session->lex->current_select->with_sum_func) ?
1833
select_limit : HA_POS_ERROR;
1835
if (!(exec_tmp_table1=
1836
create_tmp_table(session, &tmp_table_param, all_fields,
1838
group_list ? 0 : select_distinct,
1839
group_list && simple_group,
1848
We don't have to store rows in temp table that doesn't match HAVING if:
1849
- we are sorting the table and writing complete group rows to the
1851
- We are using DISTINCT without resolving the distinct as a GROUP BY
1854
If having is not handled here, it will be checked before the row
1855
is sent to the client.
1858
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1861
/* if group or order on first table, sort first */
1862
if (group_list && simple_group)
1864
session->set_proc_info("Sorting for group");
1865
if (create_sort_index(session, this, group_list,
1866
HA_POS_ERROR, HA_POS_ERROR, false) ||
1867
alloc_group_fields(this, group_list) ||
1868
make_sum_func_list(all_fields, fields_list, 1) ||
1869
setup_sum_funcs(session, sum_funcs))
1877
if (make_sum_func_list(all_fields, fields_list, 0) ||
1878
setup_sum_funcs(session, sum_funcs))
1883
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1885
session->set_proc_info("Sorting for order");
1886
if (create_sort_index(session, this, order,
1887
HA_POS_ERROR, HA_POS_ERROR, true))
1896
Optimize distinct when used on some of the tables
1897
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1898
In this case we can stop scanning t2 when we have found one t1.a
1901
if (exec_tmp_table1->distinct)
1903
table_map used_tables= session->used_tables;
1904
JOIN_TAB *last_join_tab= join_tab+tables-1;
1907
if (used_tables & last_join_tab->table->map)
1909
last_join_tab->not_used_in_distinct=1;
1910
} while (last_join_tab-- != join_tab);
1911
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1912
if (order && skip_sort_order)
1914
/* Should always succeed */
1915
if (test_if_skip_sort_order(&join_tab[const_tables],
1916
order, unit->select_limit_cnt, 0,
1917
&join_tab[const_tables].table->
1918
keys_in_use_for_order_by))
1924
If this join belongs to an uncacheable subquery save
1927
if (select_lex->uncacheable && !is_top_level_join() &&
1928
init_save_join_tab())
1929
return(-1); /* purecov: inspected */
1938
Restore values in temporary join.
1940
void JOIN::restore_tmp()
1942
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1949
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1950
select_lex->offset_limit->val_uint() :
1955
if (exec_tmp_table1)
1957
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1958
exec_tmp_table1->file->ha_delete_all_rows();
1959
free_io_cache(exec_tmp_table1);
1960
filesort_free_buffers(exec_tmp_table1,0);
1962
if (exec_tmp_table2)
1964
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1965
exec_tmp_table2->file->ha_delete_all_rows();
1966
free_io_cache(exec_tmp_table2);
1967
filesort_free_buffers(exec_tmp_table2,0);
1970
set_items_ref_array(items0);
1973
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1978
/* Reset of sum functions */
1981
Item_sum *func, **func_ptr= sum_funcs;
1982
while ((func= *(func_ptr++)))
1990
@brief Save the original join layout
1992
@details Saves the original join layout so it can be reused in
1993
re-execution and for EXPLAIN.
1995
@return Operation status
1997
@retval 1 error occurred.
2001
JOIN::init_save_join_tab()
2003
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
2004
return 1; /* purecov: inspected */
2005
error= 0; // Ensure that tmp_join.error= 0
2012
JOIN::save_join_tab()
2014
if (!join_tab_save && select_lex->master_unit()->uncacheable)
2016
if (!(join_tab_save= (JOIN_TAB*)session->memdup((unsigned char*) join_tab,
2017
sizeof(JOIN_TAB) * tables)))
2028
Note, that create_sort_index calls test_if_skip_sort_order and may
2029
finally replace sorting with index scan if there is a LIMIT clause in
2030
the query. It's never shown in EXPLAIN!
2033
When can we have here session->net.report_error not zero?
2038
List<Item> *columns_list= &fields_list;
2041
session->set_proc_info("executing");
2044
if (!tables_list && (tables || !select_lex->with_sum_func))
2046
/* Only test of functions */
2047
if (select_options & SELECT_DESCRIBE)
2048
select_describe(this, false, false, false,
2049
(zero_result_cause?zero_result_cause:"No tables used"));
2052
result->send_fields(*columns_list,
2053
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2055
We have to test for 'conds' here as the WHERE may not be constant
2056
even if we don't have any tables for prepared statements or if
2057
conds uses something like 'rand()'.
2059
if (cond_value != Item::COND_FALSE &&
2060
(!conds || conds->val_int()) &&
2061
(!having || having->val_int()))
2063
if (do_send_rows && result->send_data(fields_list))
2067
error= (int) result->send_eof();
2068
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
2073
error= (int) result->send_eof();
2077
/* Single select (without union) always returns 0 or 1 row */
2078
session->limit_found_rows= send_records;
2079
session->examined_row_count= 0;
2083
Don't reset the found rows count if there're no tables as
2084
FOUND_ROWS() may be called. Never reset the examined row count here.
2085
It must be accumulated from all join iterations of all join parts.
2088
session->limit_found_rows= 0;
2090
if (zero_result_cause)
2092
(void) return_zero_rows(this, result, select_lex->leaf_tables,
2094
send_row_on_empty_set(),
2101
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) &&
2102
get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
2105
if (select_options & SELECT_DESCRIBE)
2108
Check if we managed to optimize order_st BY away and don't use temporary
2109
table to resolve order_st BY: in that case, we only may need to do
2110
filesort for GROUP BY.
2112
if (!order && !no_order && (!skip_sort_order || !need_tmp))
2115
Reset 'order' to 'group_list' and reinit variables describing
2119
simple_order= simple_group;
2123
(order != group_list || !(select_options & SELECT_BIG_RESULT)) &&
2124
(const_tables == tables ||
2125
((simple_order || skip_sort_order) &&
2126
test_if_skip_sort_order(&join_tab[const_tables], order,
2128
&join_tab[const_tables].table->
2129
keys_in_use_for_query))))
2132
select_describe(this, need_tmp,
2133
order != 0 && !skip_sort_order,
2135
!tables ? "No tables used" : NULL);
2139
JOIN *curr_join= this;
2140
List<Item> *curr_all_fields= &all_fields;
2141
List<Item> *curr_fields_list= &fields_list;
2142
Table *curr_tmp_table= 0;
2144
Initialize examined rows here because the values from all join parts
2145
must be accumulated in examined_row_count. Hence every join
2146
iteration must count from zero.
2148
curr_join->examined_rows= 0;
2150
/* Create a tmp table if distinct or if the sort is too complicated */
2156
We are in a non cacheable sub query. Get the saved join structure
2158
(curr_join may have been modified during last exection and we need
2161
curr_join= tmp_join;
2163
curr_tmp_table= exec_tmp_table1;
2165
/* Copy data to the temporary table */
2166
session->set_proc_info("Copying to tmp table");
2167
if (!curr_join->sort_and_group &&
2168
curr_join->const_tables != curr_join->tables)
2169
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2170
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2175
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
2177
if (curr_join->having)
2178
curr_join->having= curr_join->tmp_having= 0; // Allready done
2180
/* Change sum_fields reference to calculated fields in tmp_table */
2181
curr_join->all_fields= *curr_all_fields;
2184
items1= items0 + all_fields.elements;
2185
if (sort_and_group || curr_tmp_table->group)
2187
if (change_to_use_tmp_fields(session, items1,
2188
tmp_fields_list1, tmp_all_fields1,
2189
fields_list.elements, all_fields))
2194
if (change_refs_to_tmp_fields(session, items1,
2195
tmp_fields_list1, tmp_all_fields1,
2196
fields_list.elements, all_fields))
2199
curr_join->tmp_all_fields1= tmp_all_fields1;
2200
curr_join->tmp_fields_list1= tmp_fields_list1;
2201
curr_join->items1= items1;
2203
curr_all_fields= &tmp_all_fields1;
2204
curr_fields_list= &tmp_fields_list1;
2205
curr_join->set_items_ref_array(items1);
2207
if (sort_and_group || curr_tmp_table->group)
2209
curr_join->tmp_table_param.field_count+=
2210
curr_join->tmp_table_param.sum_func_count+
2211
curr_join->tmp_table_param.func_count;
2212
curr_join->tmp_table_param.sum_func_count=
2213
curr_join->tmp_table_param.func_count= 0;
2217
curr_join->tmp_table_param.field_count+=
2218
curr_join->tmp_table_param.func_count;
2219
curr_join->tmp_table_param.func_count= 0;
2222
if (curr_tmp_table->group)
2223
{ // Already grouped
2224
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
2225
curr_join->order= curr_join->group_list; /* order by group */
2226
curr_join->group_list= 0;
2230
If we have different sort & group then we must sort the data by group
2231
and copy it to another tmp table
2232
This code is also used if we are using distinct something
2233
we haven't been able to store in the temporary table yet
2234
like SEC_TO_TIME(SUM(...)).
2237
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))
2238
{ /* Must copy to another table */
2239
/* Free first data from old join */
2240
curr_join->join_free();
2241
if (make_simple_join(curr_join, curr_tmp_table))
2243
calc_group_buffer(curr_join, group_list);
2244
count_field_types(select_lex, &curr_join->tmp_table_param,
2245
curr_join->tmp_all_fields1,
2246
curr_join->select_distinct && !curr_join->group_list);
2247
curr_join->tmp_table_param.hidden_field_count=
2248
(curr_join->tmp_all_fields1.elements-
2249
curr_join->tmp_fields_list1.elements);
2252
if (exec_tmp_table2)
2253
curr_tmp_table= exec_tmp_table2;
2256
/* group data to new table */
2259
If the access method is loose index scan then all MIN/MAX
2260
functions are precomputed, and should be treated as regular
2261
functions. See extended comment in JOIN::exec.
2263
if (curr_join->join_tab->is_using_loose_index_scan())
2264
curr_join->tmp_table_param.precomputed_group_by= true;
2266
if (!(curr_tmp_table=
2267
exec_tmp_table2= create_tmp_table(session,
2268
&curr_join->tmp_table_param,
2271
curr_join->select_distinct &&
2272
!curr_join->group_list,
2273
1, curr_join->select_options,
2277
curr_join->exec_tmp_table2= exec_tmp_table2;
2279
if (curr_join->group_list)
2281
session->set_proc_info("Creating sort index");
2282
if (curr_join->join_tab == join_tab && save_join_tab())
2286
if (create_sort_index(session, curr_join, curr_join->group_list,
2287
HA_POS_ERROR, HA_POS_ERROR, false) ||
2288
make_group_fields(this, curr_join))
2292
sortorder= curr_join->sortorder;
2295
session->set_proc_info("Copying to group table");
2297
if (curr_join != this)
2301
curr_join->sum_funcs= sum_funcs2;
2302
curr_join->sum_funcs_end= sum_funcs_end2;
2306
curr_join->alloc_func_list();
2307
sum_funcs2= curr_join->sum_funcs;
2308
sum_funcs_end2= curr_join->sum_funcs_end;
2311
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2314
curr_join->group_list= 0;
2315
if (!curr_join->sort_and_group &&
2316
curr_join->const_tables != curr_join->tables)
2317
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2318
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2319
(tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2324
end_read_record(&curr_join->join_tab->read_record);
2325
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
2326
curr_join->join_tab[0].table= 0; // Table is freed
2328
// No sum funcs anymore
2331
items2= items1 + all_fields.elements;
2332
if (change_to_use_tmp_fields(session, items2,
2333
tmp_fields_list2, tmp_all_fields2,
2334
fields_list.elements, tmp_all_fields1))
2336
curr_join->tmp_fields_list2= tmp_fields_list2;
2337
curr_join->tmp_all_fields2= tmp_all_fields2;
2339
curr_fields_list= &curr_join->tmp_fields_list2;
2340
curr_all_fields= &curr_join->tmp_all_fields2;
2341
curr_join->set_items_ref_array(items2);
2342
curr_join->tmp_table_param.field_count+=
2343
curr_join->tmp_table_param.sum_func_count;
2344
curr_join->tmp_table_param.sum_func_count= 0;
2346
if (curr_tmp_table->distinct)
2347
curr_join->select_distinct=0; /* Each row is unique */
2349
curr_join->join_free(); /* Free quick selects */
2350
if (curr_join->select_distinct && ! curr_join->group_list)
2352
session->set_proc_info("Removing duplicates");
2353
if (curr_join->tmp_having)
2354
curr_join->tmp_having->update_used_tables();
2355
if (remove_duplicates(curr_join, curr_tmp_table,
2356
*curr_fields_list, curr_join->tmp_having))
2358
curr_join->tmp_having=0;
2359
curr_join->select_distinct=0;
2361
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
2362
if (make_simple_join(curr_join, curr_tmp_table))
2364
calc_group_buffer(curr_join, curr_join->group_list);
2365
count_field_types(select_lex, &curr_join->tmp_table_param,
2366
*curr_all_fields, 0);
2370
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
2372
if (make_group_fields(this, curr_join))
2379
init_items_ref_array();
2380
items3= ref_pointer_array + (all_fields.elements*4);
2381
setup_copy_fields(session, &curr_join->tmp_table_param,
2382
items3, tmp_fields_list3, tmp_all_fields3,
2383
curr_fields_list->elements, *curr_all_fields);
2384
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
2385
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
2386
tmp_table_param.save_copy_field_end=
2387
curr_join->tmp_table_param.copy_field_end;
2388
curr_join->tmp_all_fields3= tmp_all_fields3;
2389
curr_join->tmp_fields_list3= tmp_fields_list3;
2393
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
2394
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
2395
curr_join->tmp_table_param.copy_field_end=
2396
tmp_table_param.save_copy_field_end;
2398
curr_fields_list= &tmp_fields_list3;
2399
curr_all_fields= &tmp_all_fields3;
2400
curr_join->set_items_ref_array(items3);
2402
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2404
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2405
session->is_fatal_error)
2408
if (curr_join->group_list || curr_join->order)
2410
session->set_proc_info("Sorting result");
2411
/* If we have already done the group, add HAVING to sorted table */
2412
if (curr_join->tmp_having && ! curr_join->group_list &&
2413
! curr_join->sort_and_group)
2415
// Some tables may have been const
2416
curr_join->tmp_having->update_used_tables();
2417
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
2418
table_map used_tables= (curr_join->const_table_map |
2419
curr_table->table->map);
2421
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having,
2424
if (sort_table_cond)
2426
if (!curr_table->select)
2427
if (!(curr_table->select= new SQL_SELECT))
2429
if (!curr_table->select->cond)
2430
curr_table->select->cond= sort_table_cond;
2431
else // This should never happen
2433
if (!(curr_table->select->cond=
2434
new Item_cond_and(curr_table->select->cond,
2438
Item_cond_and do not need fix_fields for execution, its parameters
2439
are fixed or do not need fix_fields, too
2441
curr_table->select->cond->quick_fix_field();
2443
curr_table->select_cond= curr_table->select->cond;
2444
curr_table->select_cond->top_level_item();
2445
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
2452
curr_join->select_limit= HA_POS_ERROR;
2456
We can abort sorting after session->select_limit rows if we there is no
2457
WHERE clause for any tables after the sorted one.
2459
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
2460
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
2461
for (; curr_table < end_table ; curr_table++)
2464
table->keyuse is set in the case there was an original WHERE clause
2465
on the table that was optimized away.
2467
if (curr_table->select_cond ||
2468
(curr_table->keyuse && !curr_table->first_inner))
2470
/* We have to sort all rows */
2471
curr_join->select_limit= HA_POS_ERROR;
2476
if (curr_join->join_tab == join_tab && save_join_tab())
2481
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
2482
chose FILESORT to be faster than INDEX SCAN or there is no
2483
suitable index present.
2484
Note, that create_sort_index calls test_if_skip_sort_order and may
2485
finally replace sorting with index scan if there is a LIMIT clause in
2486
the query. XXX: it's never shown in EXPLAIN!
2487
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
2489
if (create_sort_index(session, curr_join,
2490
curr_join->group_list ?
2491
curr_join->group_list : curr_join->order,
2492
curr_join->select_limit,
2493
(select_options & OPTION_FOUND_ROWS ?
2494
HA_POS_ERROR : unit->select_limit_cnt),
2495
curr_join->group_list ? true : false))
2497
sortorder= curr_join->sortorder;
2498
if (curr_join->const_tables != curr_join->tables &&
2499
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
2502
If no IO cache exists for the first table then we are using an
2503
INDEX SCAN and no filesort. Thus we should not remove the sorted
2504
attribute on the INDEX SCAN.
2510
/* XXX: When can we have here session->is_error() not zero? */
2511
if (session->is_error())
2513
error= session->is_error();
2516
curr_join->having= curr_join->tmp_having;
2517
curr_join->fields= curr_fields_list;
2520
session->set_proc_info("Sending data");
2521
result->send_fields(*curr_fields_list,
2522
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2523
error= do_select(curr_join, curr_fields_list, NULL);
2524
session->limit_found_rows= curr_join->send_records;
2527
/* Accumulate the counts from all join iterations of all join parts. */
2528
session->examined_row_count+= curr_join->examined_rows;
2531
With EXPLAIN EXTENDED we have to restore original ref_array
2532
for a derived table which is always materialized.
2533
Otherwise we would not be able to print the query correctly.
2536
(session->lex->describe & DESCRIBE_EXTENDED) &&
2537
select_lex->linkage == DERIVED_TABLE_TYPE)
2538
set_items_ref_array(items0);
2548
Return error that hold JOIN.
2554
select_lex->join= 0;
2558
if (join_tab != tmp_join->join_tab)
2560
JOIN_TAB *tab, *end;
2561
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
2564
tmp_join->tmp_join= 0;
2565
tmp_table_param.copy_field=0;
2566
return(tmp_join->destroy());
2571
if (exec_tmp_table1)
2572
exec_tmp_table1->free_tmp_table(session);
2573
if (exec_tmp_table2)
2574
exec_tmp_table2->free_tmp_table(session);
2576
delete_dynamic(&keyuse);
317
2583
An entry point to single-unit select (a select without UNION).
319
@param session thread Cursor
2585
@param session thread handler
320
2586
@param rref_pointer_array a reference to ref_pointer_array of
321
2587
the top-level select_lex for this query
322
2588
@param tables list of all tables used in this query.
452
2719
return(join->error);
455
inline Item *and_items(Item* cond, Item *item)
2723
int subq_sj_candidate_cmp(Item_in_subselect* const *el1,
2724
Item_in_subselect* const *el2)
2726
return ((*el1)->sj_convert_priority < (*el2)->sj_convert_priority) ? 1 :
2727
( ((*el1)->sj_convert_priority == (*el2)->sj_convert_priority)? 0 : -1);
2731
inline Item * and_items(Item* cond, Item *item)
457
2733
return (cond? (new Item_cond_and(cond, item)) : item);
2737
static TableList *alloc_join_nest(Session *session)
2740
if (!(tbl= (TableList*) session->calloc(ALIGN_SIZE(sizeof(TableList))+
2741
sizeof(nested_join_st))))
2743
tbl->nested_join= (nested_join_st*) ((unsigned char*)tbl +
2744
ALIGN_SIZE(sizeof(TableList)));
2749
void fix_list_after_tbl_changes(Select_Lex *new_parent, List<TableList> *tlist)
2751
List_iterator<TableList> it(*tlist);
2753
while ((table= it++))
2756
table->on_expr->fix_after_pullout(new_parent, &table->on_expr);
2757
if (table->nested_join)
2758
fix_list_after_tbl_changes(new_parent, &table->nested_join->join_list);
2764
Convert a subquery predicate into a TableList semi-join nest
2767
convert_subq_to_sj()
2768
parent_join Parent join, the one that has subq_pred in its WHERE/ON
2770
subq_pred Subquery predicate to be converted
2773
Convert a subquery predicate into a TableList semi-join nest. All the
2774
prerequisites are already checked, so the conversion is always successfull.
2776
Prepared Statements: the transformation is permanent:
2777
- Changes in TableList structures are naturally permanent
2778
- Item tree changes are performed on statement MEM_ROOT:
2779
= we activate statement MEM_ROOT
2780
= this function is called before the first fix_prepare_information
2783
This is intended because the criteria for subquery-to-sj conversion remain
2784
constant for the lifetime of the Prepared Statement.
2788
true Out of memory error
2791
bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
2793
Select_Lex *parent_lex= parent_join->select_lex;
2794
TableList *emb_tbl_nest= NULL;
2795
List<TableList> *emb_join_list= &parent_lex->top_join_list;
2796
Session *session= parent_join->session;
2799
1. Find out where to put the predicate into.
2800
Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
2802
if ((void*)subq_pred->expr_join_nest != (void*)1)
2804
if (subq_pred->expr_join_nest->nested_join)
2809
... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
2811
The sj-nest will be inserted into the brackets nest.
2813
emb_tbl_nest= subq_pred->expr_join_nest;
2814
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2816
else if (!subq_pred->expr_join_nest->outer_join)
2821
... INNER JOIN tblX ON (subquery AND whatever) ...
2823
The sj-nest will be tblX's "sibling", i.e. another child of its
2824
parent. This is ok because tblX is joined as an inner join.
2826
emb_tbl_nest= subq_pred->expr_join_nest->embedding;
2828
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2830
else if (!subq_pred->expr_join_nest->nested_join)
2832
TableList *outer_tbl= subq_pred->expr_join_nest;
2833
TableList *wrap_nest;
2837
... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
2839
we'll need to convert it into:
2841
... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
2843
|<----- wrap_nest ---->|
2845
Q: other subqueries may be pointing to this element. What to do?
2846
A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
2847
But we'll need to fix other pointers.
2848
A2: Another way: have TableList::next_ptr so the following
2849
subqueries know the table has been nested.
2850
A3: changes in the TableList::outer_join will make everything work
2853
if (!(wrap_nest= alloc_join_nest(parent_join->session)))
2857
wrap_nest->embedding= outer_tbl->embedding;
2858
wrap_nest->join_list= outer_tbl->join_list;
2859
wrap_nest->alias= (char*) "(sj-wrap)";
2861
wrap_nest->nested_join->join_list.empty();
2862
wrap_nest->nested_join->join_list.push_back(outer_tbl);
2864
outer_tbl->embedding= wrap_nest;
2865
outer_tbl->join_list= &wrap_nest->nested_join->join_list;
2868
wrap_nest will take place of outer_tbl, so move the outer join flag
2871
wrap_nest->outer_join= outer_tbl->outer_join;
2872
outer_tbl->outer_join= 0;
2874
wrap_nest->on_expr= outer_tbl->on_expr;
2875
outer_tbl->on_expr= NULL;
2877
List_iterator<TableList> li(*wrap_nest->join_list);
2881
if (tbl == outer_tbl)
2883
li.replace(wrap_nest);
2888
Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
2889
semi-join nest into it
2891
emb_join_list= &wrap_nest->nested_join->join_list;
2892
emb_tbl_nest= wrap_nest;
2897
nested_join_st *nested_join;
2898
if (!(sj_nest= alloc_join_nest(parent_join->session)))
2902
nested_join= sj_nest->nested_join;
2904
sj_nest->join_list= emb_join_list;
2905
sj_nest->embedding= emb_tbl_nest;
2906
sj_nest->alias= (char*) "(sj-nest)";
2907
/* Nests do not participate in those 'chains', so: */
2908
/* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
2909
emb_join_list->push_back(sj_nest);
2912
nested_join->used_tables and nested_join->not_null_tables are
2913
initialized in simplify_joins().
2917
2. Walk through subquery's top list and set 'embedding' to point to the
2920
Select_Lex *subq_lex= subq_pred->unit->first_select();
2921
nested_join->join_list.empty();
2922
List_iterator_fast<TableList> li(subq_lex->top_join_list);
2923
TableList *tl, *last_leaf;
2926
tl->embedding= sj_nest;
2927
tl->join_list= &nested_join->join_list;
2928
nested_join->join_list.push_back(tl);
2932
Reconnect the next_leaf chain.
2933
TODO: Do we have to put subquery's tables at the end of the chain?
2934
Inserting them at the beginning would be a bit faster.
2935
NOTE: We actually insert them at the front! That's because the order is
2936
reversed in this list.
2938
for (tl= parent_lex->leaf_tables; tl->next_leaf; tl= tl->next_leaf) {};
2939
tl->next_leaf= subq_lex->leaf_tables;
2943
Same as above for next_local chain
2944
(a theory: a next_local chain always starts with ::leaf_tables
2945
because view's tables are inserted after the view)
2947
for (tl= parent_lex->leaf_tables; tl->next_local; tl= tl->next_local) {};
2948
tl->next_local= subq_lex->leaf_tables;
2950
/* A theory: no need to re-connect the next_global chain */
2952
/* 3. Remove the original subquery predicate from the WHERE/ON */
2954
// The subqueries were replaced for Item_int(1) earlier
2955
subq_pred->exec_method= Item_in_subselect::SEMI_JOIN; // for subsequent executions
2956
/*TODO: also reset the 'with_subselect' there. */
2958
/* n. Adjust the parent_join->tables counter */
2959
uint32_t table_no= parent_join->tables;
2960
/* n. Walk through child's tables and adjust table->map */
2961
for (tl= subq_lex->leaf_tables; tl; tl= tl->next_leaf, table_no++)
2963
tl->table->tablenr= table_no;
2964
tl->table->map= ((table_map)1) << table_no;
2965
Select_Lex *old_sl= tl->select_lex;
2966
tl->select_lex= parent_join->select_lex;
2967
for(TableList *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)
2968
emb->select_lex= parent_join->select_lex;
2970
parent_join->tables += subq_lex->join->tables;
2973
Put the subquery's WHERE into semi-join's sj_on_expr
2974
Add the subquery-induced equalities too.
2976
Select_Lex *save_lex= session->lex->current_select;
2977
session->lex->current_select=subq_lex;
2978
if (!subq_pred->left_expr->fixed &&
2979
subq_pred->left_expr->fix_fields(session, &subq_pred->left_expr))
2981
session->lex->current_select=save_lex;
2983
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
2984
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables() |
2985
subq_pred->left_expr->used_tables();
2986
sj_nest->sj_on_expr= subq_lex->where;
2989
Create the IN-equalities and inject them into semi-join's ON expression.
2990
Additionally, for InsideOut strategy
2991
- Record the number of IN-equalities.
2992
- Create list of pointers to (oe1, ..., ieN). We'll need the list to
2993
see which of the expressions are bound and which are not (for those
2994
we'll produce a distinct stream of (ie_i1,...ie_ik).
2996
(TODO: can we just create a list of pointers and hope the expressions
2997
will not substitute themselves on fix_fields()? or we need to wrap
2998
them into Item_direct_view_refs and store pointers to those. The
2999
pointers to Item_direct_view_refs are guaranteed to be stable as
3000
Item_direct_view_refs doesn't substitute itself with anything in
3001
Item_direct_view_ref::fix_fields.
3003
sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
3004
sj_nest->nested_join->sj_outer_expr_list.empty();
3006
if (subq_pred->left_expr->cols() == 1)
3008
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr);
3010
Item *item_eq= new Item_func_eq(subq_pred->left_expr,
3011
subq_lex->ref_pointer_array[0]);
3012
item_eq->name= (char*)subq_sj_cond_name;
3013
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3017
for (uint32_t i= 0; i < subq_pred->left_expr->cols(); i++)
3019
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->
3022
new Item_func_eq(subq_pred->left_expr->element_index(i),
3023
subq_lex->ref_pointer_array[i]);
3024
item_eq->name= (char*)subq_sj_cond_name + (i % 64);
3025
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3028
/* Fix the created equality and AND */
3029
sj_nest->sj_on_expr->fix_fields(parent_join->session, &sj_nest->sj_on_expr);
3032
Walk through sj nest's WHERE and ON expressions and call
3033
item->fix_table_changes() for all items.
3035
sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr);
3036
fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
3039
/* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
3040
subq_lex->master_unit()->exclude_level();
3042
/* Inject sj_on_expr into the parent's WHERE or ON */
3045
emb_tbl_nest->on_expr= and_items(emb_tbl_nest->on_expr,
3046
sj_nest->sj_on_expr);
3047
emb_tbl_nest->on_expr->fix_fields(parent_join->session, &emb_tbl_nest->on_expr);
3051
/* Inject into the WHERE */
3052
parent_join->conds= and_items(parent_join->conds, sj_nest->sj_on_expr);
3053
parent_join->conds->fix_fields(parent_join->session, &parent_join->conds);
3054
parent_join->select_lex->where= parent_join->conds;
3062
Convert candidate subquery predicates to semi-joins
3065
JOIN::flatten_subqueries()
3068
Convert candidate subquery predicates to semi-joins.
3075
bool JOIN::flatten_subqueries()
3077
Item_in_subselect **in_subq;
3078
Item_in_subselect **in_subq_end;
3080
if (sj_subselects.elements() == 0)
3083
/* 1. Fix children subqueries */
3084
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
3085
in_subq != in_subq_end; in_subq++)
3087
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3088
child_join->outer_tables = child_join->tables;
3089
if (child_join->flatten_subqueries())
3091
(*in_subq)->sj_convert_priority=
3092
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
3095
bool outer_join_disable_semi_join= false;
3097
* Temporary measure: disable semi-joins when they are together with outer
3100
* @see LP Bug #314911
3102
for (TableList *tbl= select_lex->leaf_tables; tbl; tbl=tbl->next_leaf)
3104
TableList *embedding= tbl->embedding;
3105
if (tbl->on_expr || (tbl->embedding && !(embedding->sj_on_expr &&
3106
!embedding->embedding)))
3108
in_subq= sj_subselects.front();
3109
outer_join_disable_semi_join= true;
3113
if (! outer_join_disable_semi_join)
3116
2. Pick which subqueries to convert:
3117
sort the subquery array
3118
- prefer correlated subqueries over uncorrelated;
3119
- prefer subqueries that have greater number of outer tables;
3121
sj_subselects.sort(subq_sj_candidate_cmp);
3122
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
3123
/* Replace all subqueries to be flattened with Item_int(1) */
3124
for (in_subq= sj_subselects.front();
3125
in_subq != in_subq_end &&
3126
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3129
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
3133
for (in_subq= sj_subselects.front();
3134
in_subq != in_subq_end &&
3135
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3138
if (convert_subq_to_sj(this, *in_subq))
3143
/* 3. Finalize those we didn't convert */
3144
for (; in_subq!= in_subq_end; in_subq++)
3146
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3147
Item_subselect::trans_res res;
3148
(*in_subq)->changed= 0;
3149
(*in_subq)->fixed= 0;
3150
res= (*in_subq)->select_transformer(child_join);
3151
if (res == Item_subselect::RES_ERROR)
3154
(*in_subq)->changed= 1;
3155
(*in_subq)->fixed= 1;
3157
Item *substitute= (*in_subq)->substitution;
3158
bool do_fix_fields= !(*in_subq)->substitution->fixed;
3159
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
3162
//if ((*in_subq)->fix_fields(session, (*in_subq)->ref_ptr))
3165
sj_subselects.clear();
3171
Setup for execution all subqueries of a query, for which the optimizer
3172
chose hash semi-join.
3174
@details Iterate over all subqueries of the query, and if they are under an
3175
IN predicate, and the optimizer chose to compute it via hash semi-join:
3176
- try to initialize all data structures needed for the materialized execution
3177
of the IN predicate,
3178
- if this fails, then perform the IN=>EXISTS transformation which was
3179
previously blocked during JOIN::prepare.
3181
This method is part of the "code generation" query processing phase.
3183
This phase must be called after substitute_for_best_equal_field() because
3184
that function may replace items with other items from a multiple equality,
3185
and we need to reference the correct items in the index access method of the
3188
@return Operation status
3189
@retval false success.
3190
@retval true error occurred.
3193
bool JOIN::setup_subquery_materialization()
3195
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
3196
un= un->next_unit())
3198
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
3200
Item_subselect *subquery_predicate= sl->master_unit()->item;
3201
if (subquery_predicate &&
3202
subquery_predicate->substype() == Item_subselect::IN_SUBS)
3204
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
3205
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
3206
in_subs->setup_engine())
3216
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3219
find_eq_ref_candidate()
3220
table Table to be checked
3221
sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
3225
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3228
Check again if it is feasible to factor common parts with constant table
3232
true - There exists an eq_ref(outer-tables) candidate
3236
bool find_eq_ref_candidate(Table *table, table_map sj_inner_tables)
3238
KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
3243
while (1) /* For each key */
3246
KEY *keyinfo= table->key_info + key;
3247
key_part_map bound_parts= 0;
3248
if ((keyinfo->flags & HA_NOSAME) == HA_NOSAME)
3250
do /* For all equalities on all key parts */
3252
/* Check if this is "t.keypart = expr(outer_tables) */
3253
if (!(keyuse->used_tables & sj_inner_tables) &&
3254
!(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
3256
bound_parts |= 1 << keyuse->keypart;
3259
} while (keyuse->key == key && keyuse->table == table);
3261
if (bound_parts == PREV_BITS(uint, keyinfo->key_parts))
3263
if (keyuse->table != table)
3271
if (keyuse->table != table)
3274
while (keyuse->key == key);
3283
Pull tables out of semi-join nests, if possible
3286
pull_out_semijoin_tables()
3287
join The join where to do the semi-join flattening
3290
Try to pull tables out of semi-join nests.
3293
When this function is called, the join may have several semi-join nests
3294
(possibly within different semi-join nests), but it is guaranteed that
3295
one semi-join nest does not contain another.
3298
A table can be pulled out of the semi-join nest if
3299
- It is a constant table
3303
* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer
3305
* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.
3306
* Semi-join nests TableList::sj_inner_tables
3308
This operation is (and should be) performed at each PS execution since
3309
tables may become/cease to be constant across PS reexecutions.
3313
1 - Out of memory error
3316
int pull_out_semijoin_tables(JOIN *join)
3319
List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);
3321
/* Try pulling out of the each of the semi-joins */
3322
while ((sj_nest= sj_list_it++))
3324
/* Action #1: Mark the constant tables to be pulled out */
3325
table_map pulled_tables= 0;
3327
List_iterator<TableList> child_li(sj_nest->nested_join->join_list);
3329
while ((tbl= child_li++))
3333
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
3334
if (tbl->table->map & join->const_table_map)
3336
pulled_tables |= tbl->table->map;
3342
Action #2: Find which tables we can pull out based on
3343
update_ref_and_keys() data. Note that pulling one table out can allow
3344
us to pull out some other tables too.
3346
bool pulled_a_table;
3349
pulled_a_table= false;
3351
while ((tbl= child_li++))
3353
if (tbl->table && !(pulled_tables & tbl->table->map))
3355
if (find_eq_ref_candidate(tbl->table,
3356
sj_nest->nested_join->used_tables &
3359
pulled_a_table= true;
3360
pulled_tables |= tbl->table->map;
3364
} while (pulled_a_table);
3367
if ((sj_nest)->nested_join->used_tables == pulled_tables)
3369
(sj_nest)->sj_inner_tables= 0;
3370
while ((tbl= child_li++))
3373
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3378
/* Record the bitmap of inner tables, mark the inner tables */
3379
table_map inner_tables=(sj_nest)->nested_join->used_tables &
3381
(sj_nest)->sj_inner_tables= inner_tables;
3382
while ((tbl= child_li++))
3386
if (inner_tables & tbl->table->map)
3387
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
3389
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
460
3397
/*****************************************************************************
461
Create JoinTableS, make a guess about the table types,
3398
Create JOIN_TABS, make a guess about the table types,
462
3399
Approximate how many records will be used in each table
463
3400
*****************************************************************************/
464
ha_rows get_quick_record_count(Session *session, optimizer::SqlSelect *select, Table *table, const key_map *keys,ha_rows limit)
3403
static ha_rows get_quick_record_count(Session *session, SQL_SELECT *select,
3405
const key_map *keys,ha_rows limit)
467
3408
if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))
482
3423
return(HA_POS_ERROR); /* This shouldn't happend */
3427
This structure is used to collect info on potentially sargable
3428
predicates in order to check whether they become sargable after
3429
reading const tables.
3430
We form a bitmap of indexes that can be used for sargable predicates.
3431
Only such indexes are involved in range analysis.
3433
typedef struct st_sargable_param
3435
Field *field; /* field against which to check sargability */
3436
Item **arg_value; /* values of potential keys for lookups */
3437
uint32_t num_values; /* number of values in the above array */
3441
Calculate the best possible join and initialize the join structure.
3450
make_join_statistics(JOIN *join, TableList *tables, COND *conds,
3451
DYNAMIC_ARRAY *keyuse_array)
3455
uint32_t i,table_count,const_count,key;
3456
table_map found_const_table_map, all_table_map, found_ref, refs;
3457
key_map const_ref, eq_part;
3458
Table **table_vector;
3459
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
3460
KEYUSE *keyuse,*start_keyuse;
3461
table_map outer_join=0;
3462
SARGABLE_PARAM *sargables= 0;
3463
JOIN_TAB *stat_vector[MAX_TABLES+1];
3465
table_count=join->tables;
3466
stat=(JOIN_TAB*) join->session->calloc(sizeof(JOIN_TAB)*table_count);
3467
stat_ref=(JOIN_TAB**) join->session->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
3468
table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
3469
if (!stat || !stat_ref || !table_vector)
3470
return(1); // Eom /* purecov: inspected */
3472
join->best_ref=stat_vector;
3474
stat_end=stat+table_count;
3475
found_const_table_map= all_table_map=0;
3480
s++, tables= tables->next_leaf, i++)
3482
TableList *embedding= tables->embedding;
3485
s->const_keys.init();
3486
s->checked_keys.init();
3487
s->needed_reg.init();
3488
table_vector[i]=s->table=table=tables->table;
3489
table->pos_in_table_list= tables;
3490
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
3493
table->file->print_error(error, MYF(0));
3496
table->quick_keys.clear_all();
3497
table->reginfo.join_tab=s;
3498
table->reginfo.not_exists_optimize=0;
3499
memset(table->const_key_parts, 0,
3500
sizeof(key_part_map)*table->s->keys);
3501
all_table_map|= table->map;
3503
s->info=0; // For describe
3505
s->dependent= tables->dep_tables;
3506
s->key_dependent= 0;
3507
if (tables->schema_table)
3508
table->file->stats.records= 2;
3509
table->quick_condition_rows= table->file->stats.records;
3511
s->on_expr_ref= &tables->on_expr;
3512
if (*s->on_expr_ref)
3514
/* s is the only inner table of an outer join */
3515
if (!table->file->stats.records && !embedding)
3517
s->dependent= 0; // Ignore LEFT JOIN depend.
3518
set_position(join,const_count++,s,(KEYUSE*) 0);
3521
outer_join|= table->map;
3522
s->embedding_map= 0;
3523
for (;embedding; embedding= embedding->embedding)
3524
s->embedding_map|= embedding->nested_join->nj_map;
3527
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
3529
/* s belongs to a nested join, maybe to several embedded joins */
3530
s->embedding_map= 0;
3533
nested_join_st *nested_join= embedding->nested_join;
3534
s->embedding_map|=nested_join->nj_map;
3535
s->dependent|= embedding->dep_tables;
3536
embedding= embedding->embedding;
3537
outer_join|= nested_join->used_tables;
3542
if ((table->file->stats.records <= 1) &&
3544
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && !join->no_const_tables)
3546
set_position(join,const_count++,s,(KEYUSE*) 0);
3550
join->outer_join=outer_join;
3552
if (join->outer_join)
3555
Build transitive closure for relation 'to be dependent on'.
3556
This will speed up the plan search for many cases with outer joins,
3557
as well as allow us to catch illegal cross references/
3558
Warshall's algorithm is used to build the transitive closure.
3559
As we use bitmaps to represent the relation the complexity
3560
of the algorithm is O((number of tables)^2).
3562
for (i= 0, s= stat ; i < table_count ; i++, s++)
3564
for (uint32_t j= 0 ; j < table_count ; j++)
3566
table= stat[j].table;
3567
if (s->dependent & table->map)
3568
s->dependent |= table->reginfo.join_tab->dependent;
3571
s->table->maybe_null= 1;
3573
/* Catch illegal cross references for outer joins */
3574
for (i= 0, s= stat ; i < table_count ; i++, s++)
3576
if (s->dependent & s->table->map)
3578
join->tables=0; // Don't use join->table
3579
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
3582
s->key_dependent= s->dependent;
3586
if (conds || outer_join)
3587
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
3588
conds, join->cond_equal,
3589
~outer_join, join->select_lex, &sargables))
3592
/* Read tables with 0 or 1 rows (system tables) */
3593
join->const_table_map= 0;
3595
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
3602
join->const_table_map|=s->table->map;
3603
if ((tmp=join_read_const_table(s, p_pos)))
3606
return(1); // Fatal error
3609
found_const_table_map|= s->table->map;
3612
/* loop until no more const tables are found */
3616
more_const_tables_found:
3621
We only have to loop from stat_vector + const_count as
3622
set_position() will move all const_tables first in stat_vector
3625
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
3630
If equi-join condition by a key is null rejecting and after a
3631
substitution of a const table the key value happens to be null
3632
then we can state that there are no matches for this equi-join.
3634
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
3637
When performing an outer join operation if there are no matching rows
3638
for the single row of the outer table all the inner tables are to be
3639
null complemented and thus considered as constant tables.
3640
Here we apply this consideration to the case of outer join operations
3641
with a single inner table only because the case with nested tables
3642
would require a more thorough analysis.
3643
TODO. Apply single row substitution to null complemented inner tables
3644
for nested outer join operations.
3646
while (keyuse->table == table)
3648
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
3649
keyuse->val->is_null() && keyuse->null_rejecting)
3652
mark_as_null_row(table);
3653
found_const_table_map|= table->map;
3654
join->const_table_map|= table->map;
3655
set_position(join,const_count++,s,(KEYUSE*) 0);
3656
goto more_const_tables_found;
3662
if (s->dependent) // If dependent on some table
3664
// All dep. must be constants
3665
if (s->dependent & ~(found_const_table_map))
3667
if (table->file->stats.records <= 1L &&
3668
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
3669
!table->pos_in_table_list->embedding)
3673
join->const_table_map|=table->map;
3674
set_position(join,const_count++,s,(KEYUSE*) 0);
3675
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
3678
return(1); // Fatal error
3681
found_const_table_map|= table->map;
3685
/* check if table can be read by key or table only uses const refs */
3686
if ((keyuse=s->keyuse))
3689
while (keyuse->table == table)
3691
start_keyuse=keyuse;
3693
s->keys.set_bit(key); // QQ: remove this ?
3696
const_ref.clear_all();
3697
eq_part.clear_all();
3700
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
3702
if (!((~found_const_table_map) & keyuse->used_tables))
3703
const_ref.set_bit(keyuse->keypart);
3705
refs|=keyuse->used_tables;
3706
eq_part.set_bit(keyuse->keypart);
3709
} while (keyuse->table == table && keyuse->key == key);
3711
if (eq_part.is_prefix(table->key_info[key].key_parts) &&
3712
!table->pos_in_table_list->embedding)
3714
if ((table->key_info[key].flags & (HA_NOSAME))
3717
if (const_ref == eq_part)
3718
{ // Found everything for ref.
3722
join->const_table_map|=table->map;
3723
set_position(join,const_count++,s,start_keyuse);
3724
if (create_ref_for_key(join, s, start_keyuse,
3725
found_const_table_map))
3727
if ((tmp=join_read_const_table(s,
3728
join->positions+const_count-1)))
3731
return(1); // Fatal error
3734
found_const_table_map|= table->map;
3738
found_ref|= refs; // Table is const if all refs are const
3740
else if (const_ref == eq_part)
3741
s->const_keys.set_bit(key);
3746
} while (join->const_table_map & found_ref && ref_changed);
3749
Update info on indexes that can be used for search lookups as
3750
reading const tables may has added new sargable predicates.
3752
if (const_count && sargables)
3754
for( ; sargables->field ; sargables++)
3756
Field *field= sargables->field;
3757
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
3758
key_map possible_keys= field->key_start;
3759
possible_keys.intersect(field->table->keys_in_use_for_query);
3761
for (uint32_t j=0; j < sargables->num_values; j++)
3762
is_const&= sargables->arg_value[j]->const_item();
3764
join_tab[0].const_keys.merge(possible_keys);
3768
if (pull_out_semijoin_tables(join))
3771
/* Calc how many (possible) matched records in each table */
3773
for (s=stat ; s < stat_end ; s++)
3775
if (s->type == JT_SYSTEM || s->type == JT_CONST)
3777
/* Only one matching row */
3778
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
3781
/* Approximate found rows and time to read them */
3782
s->found_records=s->records=s->table->file->stats.records;
3783
s->read_time=(ha_rows) s->table->file->scan_time();
3786
Set a max range of how many seeks we can expect when using keys
3787
This is can't be to high as otherwise we are likely to use
3790
s->worst_seeks= cmin((double) s->found_records / 10,
3791
(double) s->read_time*3);
3792
if (s->worst_seeks < 2.0) // Fix for small tables
3796
Add to stat->const_keys those indexes for which all group fields or
3797
all select distinct fields participate in one index.
3799
add_group_and_distinct_keys(join, s);
3801
if (!s->const_keys.is_clear_all() &&
3802
!s->table->pos_in_table_list->embedding)
3806
select= make_select(s->table, found_const_table_map,
3807
found_const_table_map,
3808
*s->on_expr_ref ? *s->on_expr_ref : conds,
3812
records= get_quick_record_count(join->session, select, s->table,
3813
&s->const_keys, join->row_limit);
3814
s->quick=select->quick;
3815
s->needed_reg=select->needed_reg;
3817
if (records == 0 && s->table->reginfo.impossible_range)
3820
Impossible WHERE or ON expression
3821
In case of ON, we mark that the we match one empty NULL row.
3822
In case of WHERE, don't set found_const_table_map to get the
3823
caller to abort with a zero row result.
3825
join->const_table_map|= s->table->map;
3826
set_position(join,const_count++,s,(KEYUSE*) 0);
3828
if (*s->on_expr_ref)
3830
/* Generate empty row */
3831
s->info= "Impossible ON condition";
3832
found_const_table_map|= s->table->map;
3834
mark_as_null_row(s->table); // All fields are NULL
3837
if (records != HA_POS_ERROR)
3839
s->found_records=records;
3840
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
3846
join->join_tab=stat;
3847
join->map2table=stat_ref;
3848
join->table= join->all_tables=table_vector;
3849
join->const_tables=const_count;
3850
join->found_const_table_map=found_const_table_map;
3852
/* Find an optimal join order of the non-constant tables. */
3853
if (join->const_tables != join->tables)
3855
optimize_keyuse(join, keyuse_array);
3856
if (choose_plan(join, all_table_map & ~join->const_table_map))
3861
memcpy(join->best_positions, join->positions,
3862
sizeof(POSITION)*join->const_tables);
3863
join->best_read=1.0;
3865
/* Generate an execution plan from the found optimal join order. */
3866
return(join->session->killed || get_best_combination(join));
485
3870
/*****************************************************************************
486
3871
Check with keys are used and with tables references with tables
487
3872
Updates in stat:
490
3875
keyuse Pointer to possible keys
491
3876
*****************************************************************************/
3878
/// Used when finding key fields
3879
typedef struct key_field_t {
3881
Item *val; ///< May be empty if diff constant
3883
uint optimize; // KEY_OPTIMIZE_*
3886
If true, the condition this struct represents will not be satisfied
3889
bool null_rejecting;
3890
bool *cond_guard; /* See KEYUSE::cond_guard */
3891
uint32_t sj_pred_no; /* See KEYUSE::sj_pred_no */
3895
Merge new key definitions to old ones, remove those not used in both.
3897
This is called for OR between different levels.
3899
To be able to do 'ref_or_null' we merge a comparison of a column
3900
and 'column IS NULL' to one test. This is useful for sub select queries
3901
that are internally transformed to something like:.
3904
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
3907
KEY_FIELD::null_rejecting is processed as follows: @n
3908
result has null_rejecting=true if it is set for both ORed references.
3910
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
3911
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
3914
The result of this is that we're missing some 'ref' accesses.
3915
OptimizerTeam: Fix this
3919
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
3922
if (start == new_fields)
3923
return start; // Impossible or
3924
if (new_fields == end)
3925
return start; // No new fields, skip all
3927
KEY_FIELD *first_free=new_fields;
3929
/* Mark all found fields in old array */
3930
for (; new_fields != end ; new_fields++)
3932
for (KEY_FIELD *old=start ; old != first_free ; old++)
3934
if (old->field == new_fields->field)
3937
NOTE: below const_item() call really works as "!used_tables()", i.e.
3938
it can return false where it is feasible to make it return true.
3940
The cause is as follows: Some of the tables are already known to be
3941
const tables (the detection code is in make_join_statistics(),
3942
above the update_ref_and_keys() call), but we didn't propagate
3943
information about this: Table::const_table is not set to true, and
3944
Item::update_used_tables() hasn't been called for each item.
3945
The result of this is that we're missing some 'ref' accesses.
3946
TODO: OptimizerTeam: Fix this
3948
if (!new_fields->val->const_item())
3951
If the value matches, we can use the key reference.
3952
If not, we keep it until we have examined all new values
3954
if (old->val->eq(new_fields->val, old->field->binary()))
3956
old->level= and_level;
3957
old->optimize= ((old->optimize & new_fields->optimize &
3958
KEY_OPTIMIZE_EXISTS) |
3959
((old->optimize | new_fields->optimize) &
3960
KEY_OPTIMIZE_REF_OR_NULL));
3961
old->null_rejecting= (old->null_rejecting &&
3962
new_fields->null_rejecting);
3965
else if (old->eq_func && new_fields->eq_func &&
3966
old->val->eq_by_collation(new_fields->val,
3967
old->field->binary(),
3968
old->field->charset()))
3971
old->level= and_level;
3972
old->optimize= ((old->optimize & new_fields->optimize &
3973
KEY_OPTIMIZE_EXISTS) |
3974
((old->optimize | new_fields->optimize) &
3975
KEY_OPTIMIZE_REF_OR_NULL));
3976
old->null_rejecting= (old->null_rejecting &&
3977
new_fields->null_rejecting);
3979
else if (old->eq_func && new_fields->eq_func &&
3980
((old->val->const_item() && old->val->is_null()) ||
3981
new_fields->val->is_null()))
3983
/* field = expression OR field IS NULL */
3984
old->level= and_level;
3985
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
3987
Remember the NOT NULL value unless the value does not depend
3990
if (!old->val->used_tables() && old->val->is_null())
3991
old->val= new_fields->val;
3992
/* The referred expression can be NULL: */
3993
old->null_rejecting= 0;
3998
We are comparing two different const. In this case we can't
3999
use a key-lookup on this so it's better to remove the value
4000
and let the range optimzier handle it
4002
if (old == --first_free) // If last item
4004
*old= *first_free; // Remove old value
4005
old--; // Retry this value
4010
/* Remove all not used items */
4011
for (KEY_FIELD *old=start ; old != first_free ;)
4013
if (old->level != and_level)
4014
{ // Not used in all levels
4015
if (old == --first_free)
4017
*old= *first_free; // Remove old value
4027
Add a possible key to array of possible keys if it's usable as a key
4029
@param key_fields Pointer to add key, if usable
4030
@param and_level And level, to be stored in KEY_FIELD
4031
@param cond Condition predicate
4032
@param field Field used in comparision
4033
@param eq_func True if we used =, <=> or IS NULL
4034
@param value Value used for comparison with field
4035
@param usable_tables Tables which can be used for key optimization
4036
@param sargables IN/OUT Array of found sargable candidates
4039
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
4040
table, we store this to be able to do not exists optimization later.
4043
*key_fields is incremented if we stored a key in the array
4047
add_key_field(KEY_FIELD **key_fields,uint32_t and_level, Item_func *cond,
4048
Field *field, bool eq_func, Item **value, uint32_t num_values,
4049
table_map usable_tables, SARGABLE_PARAM **sargables)
4051
uint32_t exists_optimize= 0;
4052
if (!(field->flags & PART_KEY_FLAG))
4054
// Don't remove column IS NULL on a LEFT JOIN table
4055
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4056
!field->table->maybe_null || field->null_ptr)
4057
return; // Not a key. Skip it
4058
exists_optimize= KEY_OPTIMIZE_EXISTS;
4059
assert(num_values == 1);
4063
table_map used_tables=0;
4065
for (uint32_t i=0; i<num_values; i++)
4067
used_tables|=(value[i])->used_tables();
4068
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
4073
if (!(usable_tables & field->table->map))
4075
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4076
!field->table->maybe_null || field->null_ptr)
4077
return; // Can't use left join optimize
4078
exists_optimize= KEY_OPTIMIZE_EXISTS;
4082
JOIN_TAB *stat=field->table->reginfo.join_tab;
4083
key_map possible_keys=field->key_start;
4084
possible_keys.intersect(field->table->keys_in_use_for_query);
4085
stat[0].keys.merge(possible_keys); // Add possible keys
4088
Save the following cases:
4090
Field LIKE constant where constant doesn't start with a wildcard
4091
Field = field2 where field2 is in a different table
4098
stat[0].key_dependent|=used_tables;
4101
for (uint32_t i=0; i<num_values; i++)
4103
if (!(is_const&= value[i]->const_item()))
4107
stat[0].const_keys.merge(possible_keys);
4111
Save info to be able check whether this predicate can be
4112
considered as sargable for range analisis after reading const tables.
4113
We do not save info about equalities as update_const_equal_items
4114
will take care of updating info on keys from sargable equalities.
4117
(*sargables)->field= field;
4118
(*sargables)->arg_value= value;
4119
(*sargables)->num_values= num_values;
4122
We can't always use indexes when comparing a string index to a
4123
number. cmp_type() is checked to allow compare of dates to numbers.
4124
eq_func is NEVER true when num_values > 1
4129
Additional optimization: if we're processing
4130
"t.key BETWEEN c1 AND c1" then proceed as if we were processing
4132
TODO: This is a very limited fix. A more generic fix is possible.
4133
There are 2 options:
4134
A) Make equality propagation code be able to handle BETWEEN
4135
(including cases like t1.key BETWEEN t2.key AND t3.key)
4136
B) Make range optimizer to infer additional "t.key = c" equalities
4137
and use them in equality propagation process (see details in
4140
if ((cond->functype() != Item_func::BETWEEN) ||
4141
((Item_func_between*) cond)->negated ||
4142
!value[0]->eq(value[1], field->binary()))
4147
if (field->result_type() == STRING_RESULT)
4149
if ((*value)->result_type() != STRING_RESULT)
4151
if (field->cmp_type() != (*value)->result_type())
4157
We can't use indexes if the effective collation
4158
of the operation differ from the field collation.
4160
if (field->cmp_type() == STRING_RESULT &&
4161
((Field_str*)field)->charset() != cond->compare_collation())
4168
For the moment eq_func is always true. This slot is reserved for future
4169
extensions where we want to remembers other things than just eq comparisons
4172
/* Store possible eq field */
4173
(*key_fields)->field= field;
4174
(*key_fields)->eq_func= eq_func;
4175
(*key_fields)->val= *value;
4176
(*key_fields)->level= and_level;
4177
(*key_fields)->optimize= exists_optimize;
4179
If the condition has form "tbl.keypart = othertbl.field" and
4180
othertbl.field can be NULL, there will be no matches if othertbl.field
4182
We use null_rejecting in add_not_null_conds() to add
4183
'othertbl.field IS NOT NULL' to tab->select_cond.
4185
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
4186
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
4187
((*value)->type() == Item::FIELD_ITEM) &&
4188
((Item_field*)*value)->field->maybe_null());
4189
(*key_fields)->cond_guard= NULL;
4190
(*key_fields)->sj_pred_no= (cond->name >= subq_sj_cond_name &&
4191
cond->name < subq_sj_cond_name + 64)?
4192
cond->name - subq_sj_cond_name: UINT_MAX;
4197
Add possible keys to array of possible keys originated from a simple
4200
@param key_fields Pointer to add key, if usable
4201
@param and_level And level, to be stored in KEY_FIELD
4202
@param cond Condition predicate
4203
@param field Field used in comparision
4204
@param eq_func True if we used =, <=> or IS NULL
4205
@param value Value used for comparison with field
4206
Is NULL for BETWEEN and IN
4207
@param usable_tables Tables which can be used for key optimization
4208
@param sargables IN/OUT Array of found sargable candidates
4211
If field items f1 and f2 belong to the same multiple equality and
4212
a key is added for f1, the the same key is added for f2.
4215
*key_fields is incremented if we stored a key in the array
4219
add_key_equal_fields(KEY_FIELD **key_fields, uint32_t and_level,
4220
Item_func *cond, Item_field *field_item,
4221
bool eq_func, Item **val,
4222
uint32_t num_values, table_map usable_tables,
4223
SARGABLE_PARAM **sargables)
4225
Field *field= field_item->field;
4226
add_key_field(key_fields, and_level, cond, field,
4227
eq_func, val, num_values, usable_tables, sargables);
4228
Item_equal *item_equal= field_item->item_equal;
4232
Add to the set of possible key values every substitution of
4233
the field for an equal field included into item_equal
4235
Item_equal_iterator it(*item_equal);
4237
while ((item= it++))
4239
if (!field->eq(item->field))
4241
add_key_field(key_fields, and_level, cond, item->field,
4242
eq_func, val, num_values, usable_tables,
4250
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint32_t *and_level,
4251
COND *cond, table_map usable_tables,
4252
SARGABLE_PARAM **sargables)
4254
if (cond->type() == Item_func::COND_ITEM)
4256
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
4257
KEY_FIELD *org_key_fields= *key_fields;
4259
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
4263
add_key_fields(join, key_fields, and_level, item, usable_tables,
4265
for (; org_key_fields != *key_fields ; org_key_fields++)
4266
org_key_fields->level= *and_level;
4271
add_key_fields(join, key_fields, and_level, li++, usable_tables,
4276
KEY_FIELD *start_key_fields= *key_fields;
4278
add_key_fields(join, key_fields, and_level, item, usable_tables,
4280
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
4281
*key_fields,++(*and_level));
4288
Subquery optimization: Conditions that are pushed down into subqueries
4289
are wrapped into Item_func_trig_cond. We process the wrapped condition
4290
but need to set cond_guard for KEYUSE elements generated from it.
4293
if (cond->type() == Item::FUNC_ITEM &&
4294
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
4296
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
4297
if (!join->group_list && !join->order &&
4299
join->unit->item->substype() == Item_subselect::IN_SUBS &&
4300
!join->unit->is_union())
4302
KEY_FIELD *save= *key_fields;
4303
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
4305
// Indicate that this ref access candidate is for subquery lookup:
4306
for (; save != *key_fields; save++)
4307
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
4313
/* If item is of type 'field op field/constant' add it to key_fields */
4314
if (cond->type() != Item::FUNC_ITEM)
4316
Item_func *cond_func= (Item_func*) cond;
4317
switch (cond_func->select_optimize()) {
4318
case Item_func::OPTIMIZE_NONE:
4320
case Item_func::OPTIMIZE_KEY:
4324
if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
4325
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4327
values= cond_func->arguments()+1;
4328
if (cond_func->functype() == Item_func::NE_FUNC &&
4329
cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4330
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4332
assert(cond_func->functype() != Item_func::IN_FUNC ||
4333
cond_func->argument_count() != 2);
4334
add_key_equal_fields(key_fields, *and_level, cond_func,
4335
(Item_field*) (cond_func->key_item()->real_item()),
4337
cond_func->argument_count()-1,
4338
usable_tables, sargables);
4340
if (cond_func->functype() == Item_func::BETWEEN)
4342
values= cond_func->arguments();
4343
for (uint32_t i= 1 ; i < cond_func->argument_count() ; i++)
4345
Item_field *field_item;
4346
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
4348
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
4350
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
4351
add_key_equal_fields(key_fields, *and_level, cond_func,
4352
field_item, 0, values, 1, usable_tables,
4359
case Item_func::OPTIMIZE_OP:
4361
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
4362
cond_func->functype() == Item_func::EQUAL_FUNC);
4364
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4365
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4367
add_key_equal_fields(key_fields, *and_level, cond_func,
4368
(Item_field*) (cond_func->arguments()[0])->real_item(),
4370
cond_func->arguments()+1, 1, usable_tables,
4373
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4374
cond_func->functype() != Item_func::LIKE_FUNC &&
4375
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
4377
add_key_equal_fields(key_fields, *and_level, cond_func,
4378
(Item_field*) (cond_func->arguments()[1])->real_item(),
4380
cond_func->arguments(),1,usable_tables,
4385
case Item_func::OPTIMIZE_NULL:
4386
/* column_name IS [NOT] NULL */
4387
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4388
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4390
Item *tmp=new Item_null;
4391
if (unlikely(!tmp)) // Should never be true
4393
add_key_equal_fields(key_fields, *and_level, cond_func,
4394
(Item_field*) (cond_func->arguments()[0])->real_item(),
4395
cond_func->functype() == Item_func::ISNULL_FUNC,
4396
&tmp, 1, usable_tables, sargables);
4399
case Item_func::OPTIMIZE_EQUAL:
4400
Item_equal *item_equal= (Item_equal *) cond;
4401
Item *const_item= item_equal->get_const();
4402
Item_equal_iterator it(*item_equal);
4407
For each field field1 from item_equal consider the equality
4408
field1=const_item as a condition allowing an index access of the table
4409
with field1 by the keys value of field1.
4411
while ((item= it++))
4413
add_key_field(key_fields, *and_level, cond_func, item->field,
4414
true, &const_item, 1, usable_tables, sargables);
4420
Consider all pairs of different fields included into item_equal.
4421
For each of them (field1, field1) consider the equality
4422
field1=field2 as a condition allowing an index access of the table
4423
with field1 by the keys value of field2.
4425
Item_equal_iterator fi(*item_equal);
4426
while ((item= fi++))
4428
Field *field= item->field;
4429
while ((item= it++))
4431
if (!field->eq(item->field))
4433
add_key_field(key_fields, *and_level, cond_func, field,
4434
true, (Item **) &item, 1, usable_tables,
495
4446
Add all keys with uses 'field' for some keypart.
497
4448
If field->and_level != and_level then only mark key_part as const_part.
499
uint32_t max_part_bit(key_part_map bits)
4452
max_part_bit(key_part_map bits)
502
4455
for (found=0; bits & 1 ; found++,bits>>=1) ;
506
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)
4460
add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
4462
Field *field=key_field->field;
4463
Table *form= field->table;
4466
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
4468
for (uint32_t key= 0 ; key < form->sizeKeys() ; key++)
4470
if (!(form->keys_in_use_for_query.is_set(key)))
4473
uint32_t key_parts= (uint32_t) form->key_info[key].key_parts;
4474
for (uint32_t part=0 ; part < key_parts ; part++)
4476
if (field->eq(form->key_info[key].key_part[part].field))
4478
keyuse.table= field->table;
4479
keyuse.val = key_field->val;
4481
keyuse.keypart=part;
4482
keyuse.keypart_map= (key_part_map) 1 << part;
4483
keyuse.used_tables=key_field->val->used_tables();
4484
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
4485
keyuse.null_rejecting= key_field->null_rejecting;
4486
keyuse.cond_guard= key_field->cond_guard;
4487
keyuse.sj_pred_no= key_field->sj_pred_no;
4488
insert_dynamic(keyuse_array,(unsigned char*) &keyuse);
4496
sort_keyuse(KEYUSE *a,KEYUSE *b)
509
if (a->getTable()->tablenr != b->getTable()->tablenr)
510
return static_cast<int>((a->getTable()->tablenr - b->getTable()->tablenr));
511
if (a->getKey() != b->getKey())
512
return static_cast<int>((a->getKey() - b->getKey()));
513
if (a->getKeypart() != b->getKeypart())
514
return static_cast<int>((a->getKeypart() - b->getKeypart()));
4499
if (a->table->tablenr != b->table->tablenr)
4500
return (int) (a->table->tablenr - b->table->tablenr);
4501
if (a->key != b->key)
4502
return (int) (a->key - b->key);
4503
if (a->keypart != b->keypart)
4504
return (int) (a->keypart - b->keypart);
515
4505
// Place const values before other ones
516
if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -
517
test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))
4506
if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
4507
test((b->used_tables & ~OUTER_REF_TABLE_BIT))))
519
4509
/* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
520
return static_cast<int>(((a->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) -
521
(b->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)));
4510
return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
4511
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
4516
Add to KEY_FIELD array all 'ref' access candidates within nested join.
4518
This function populates KEY_FIELD array with entries generated from the
4519
ON condition of the given nested join, and does the same for nested joins
4520
contained within this nested join.
4522
@param[in] nested_join_table Nested join pseudo-table to process
4523
@param[in,out] end End of the key field array
4524
@param[in,out] and_level And-level
4525
@param[in,out] sargables Array of found sargable candidates
4529
We can add accesses to the tables that are direct children of this nested
4530
join (1), and are not inner tables w.r.t their neighbours (2).
4532
Example for #1 (outer brackets pair denotes nested join this function is
4535
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
4539
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
4541
In examples 1-2 for condition cond, we can add 'ref' access candidates to
4545
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
4547
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
4550
static void add_key_fields_for_nj(JOIN *join, TableList *nested_join_table,
4551
KEY_FIELD **end, uint32_t *and_level,
4552
SARGABLE_PARAM **sargables)
4554
List_iterator<TableList> li(nested_join_table->nested_join->join_list);
4555
List_iterator<TableList> li2(nested_join_table->nested_join->join_list);
4556
bool have_another = false;
4557
table_map tables= 0;
4559
assert(nested_join_table->nested_join);
4561
while ((table= li++) || (have_another && (li=li2, have_another=false,
4564
if (table->nested_join)
4566
if (!table->on_expr)
4568
/* It's a semi-join nest. Walk into it as if it wasn't a nest */
4571
li= List_iterator<TableList>(table->nested_join->join_list);
4574
add_key_fields_for_nj(join, table, end, and_level, sargables);
4577
if (!table->on_expr)
4578
tables |= table->table->map;
4580
if (nested_join_table->on_expr)
4581
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
781
4845
/* Intersect the keys of all group fields. */
782
4846
cur_item= indexed_fields_it++;
783
possible_keys|= cur_item->field->part_of_key;
4847
possible_keys.merge(cur_item->field->part_of_key);
784
4848
while ((cur_item= indexed_fields_it++))
786
possible_keys&= cur_item->field->part_of_key;
789
if (possible_keys.any())
790
join_tab->const_keys|= possible_keys;
794
Compare two JoinTable objects based on the number of accessed records.
796
@param ptr1 pointer to first JoinTable object
797
@param ptr2 pointer to second JoinTable object
4850
possible_keys.intersect(cur_item->field->part_of_key);
4853
if (!possible_keys.is_clear_all())
4854
join_tab->const_keys.merge(possible_keys);
4858
/*****************************************************************************
4859
Go through all combinations of not marked tables and find the one
4860
which uses least records
4861
*****************************************************************************/
4863
/** Save const tables first as used tables. */
4866
set_position(JOIN *join,uint32_t idx,JOIN_TAB *table,KEYUSE *key)
4868
join->positions[idx].table= table;
4869
join->positions[idx].key=key;
4870
join->positions[idx].records_read=1.0; /* This is a const table */
4871
join->positions[idx].ref_depend_map= 0;
4873
/* Move the const table as down as possible in best_ref */
4874
JOIN_TAB **pos=join->best_ref+idx+1;
4875
JOIN_TAB *next=join->best_ref[idx];
4876
for (;next != table ; pos++)
4878
JOIN_TAB *tmp=pos[0];
4882
join->best_ref[idx]=table;
4887
Given a semi-join nest, find out which of the IN-equalities are bound
4890
get_bound_sj_equalities()
4891
sj_nest Semi-join nest
4892
remaining_tables Tables that are not yet bound
4895
Given a semi-join nest, find out which of the IN-equalities have their
4896
left part expression bound (i.e. the said expression doesn't refer to
4897
any of remaining_tables and can be evaluated).
4900
Bitmap of bound IN-equalities.
4903
uint64_t get_bound_sj_equalities(TableList *sj_nest,
4904
table_map remaining_tables)
4906
List_iterator<Item> li(sj_nest->nested_join->sj_outer_expr_list);
4910
while ((item= li++))
4913
Q: should this take into account equality propagation and how?
4914
A: If e->outer_side is an Item_field, walk over the equality
4915
class and see if there is an element that is bound?
4916
(this is an optional feature)
4918
if (!(item->used_tables() & remaining_tables))
4928
Find the best access path for an extension of a partial execution
4929
plan and add this path to the plan.
4931
The function finds the best access path to table 's' from the passed
4932
partial plan where an access path is the general term for any means to
4933
access the data in 's'. An access path may use either an index or a scan,
4934
whichever is cheaper. The input partial plan is passed via the array
4935
'join->positions' of length 'idx'. The chosen access method for 's' and its
4936
cost are stored in 'join->positions[idx]'.
4938
@param join pointer to the structure providing all context info
4940
@param s the table to be joined by the function
4941
@param session thread for the connection that submitted the query
4942
@param remaining_tables set of tables not included into the partial plan yet
4943
@param idx the length of the partial plan
4944
@param record_count estimate for the number of records returned by the
4946
@param read_time the cost of the partial plan
4953
best_access_path(JOIN *join,
4956
table_map remaining_tables,
4958
double record_count,
4961
KEYUSE *best_key= 0;
4962
uint32_t best_max_key_part= 0;
4963
bool found_constraint= 0;
4964
double best= DBL_MAX;
4965
double best_time= DBL_MAX;
4966
double records= DBL_MAX;
4967
table_map best_ref_depends_map= 0;
4970
uint32_t best_is_sj_inside_out= 0;
4973
{ /* Use key if possible */
4974
Table *table= s->table;
4975
KEYUSE *keyuse,*start_key=0;
4976
double best_records= DBL_MAX;
4977
uint32_t max_key_part=0;
4978
uint64_t bound_sj_equalities= 0;
4979
bool try_sj_inside_out= false;
4981
Discover the bound equalites. We need to do this, if
4982
1. The next table is an SJ-inner table, and
4983
2. It is the first table from that semijoin, and
4984
3. We're not within a semi-join range (i.e. all semi-joins either have
4985
all or none of their tables in join_table_map), except
4986
s->emb_sj_nest (which we've just entered).
4987
3. All correlation references from this sj-nest are bound
4989
if (s->emb_sj_nest && // (1)
4990
s->emb_sj_nest->sj_in_exprs < 64 &&
4991
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
4992
s->emb_sj_nest->sj_inner_tables) && // (2)
4993
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
4994
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
4996
/* This table is an InsideOut scan candidate */
4997
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
4999
try_sj_inside_out= true;
5002
/* Test how we can use keys */
5003
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
5004
for (keyuse=s->keyuse ; keyuse->table == table ;)
5006
key_part_map found_part= 0;
5007
table_map found_ref= 0;
5008
uint32_t key= keyuse->key;
5009
KEY *keyinfo= table->key_info+key;
5010
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
5011
key_part_map const_part= 0;
5012
/* The or-null keypart in ref-or-null access: */
5013
key_part_map ref_or_null_part= 0;
5015
/* Calculate how many key segments of the current key we can use */
5017
uint64_t handled_sj_equalities=0;
5018
key_part_map sj_insideout_map= 0;
5020
do /* For each keypart */
5022
uint32_t keypart= keyuse->keypart;
5023
table_map best_part_found_ref= 0;
5024
double best_prev_record_reads= DBL_MAX;
5026
do /* For each way to access the keypart */
5030
if 1. expression doesn't refer to forward tables
5031
2. we won't get two ref-or-null's
5033
if (!(remaining_tables & keyuse->used_tables) &&
5034
!(ref_or_null_part && (keyuse->optimize &
5035
KEY_OPTIMIZE_REF_OR_NULL)))
5037
found_part|= keyuse->keypart_map;
5038
if (!(keyuse->used_tables & ~join->const_table_map))
5039
const_part|= keyuse->keypart_map;
5041
double tmp2= prev_record_reads(join, idx, (found_ref |
5042
keyuse->used_tables));
5043
if (tmp2 < best_prev_record_reads)
5045
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
5046
best_prev_record_reads= tmp2;
5048
if (rec > keyuse->ref_table_rows)
5049
rec= keyuse->ref_table_rows;
5051
If there is one 'key_column IS NULL' expression, we can
5052
use this ref_or_null optimisation of this field
5054
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
5055
ref_or_null_part |= keyuse->keypart_map;
5058
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
5060
if (!(remaining_tables & keyuse->used_tables))
5061
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
5064
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
5065
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
5070
} while (keyuse->table == table && keyuse->key == key &&
5071
keyuse->keypart == keypart);
5072
found_ref|= best_part_found_ref;
5073
} while (keyuse->table == table && keyuse->key == key);
5076
Assume that that each key matches a proportional part of table.
5078
if (!found_part && !handled_sj_equalities)
5079
continue; // Nothing usable found
5081
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
5082
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
5084
bool sj_inside_out_scan= false;
5086
found_constraint= 1;
5088
Check if InsideOut scan is applicable:
5089
1. All IN-equalities are either "bound" or "handled"
5090
2. Index keyparts are
5093
if (try_sj_inside_out &&
5094
table->covering_keys.is_set(key) &&
5095
(handled_sj_equalities | bound_sj_equalities) == // (1)
5096
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
5098
uint32_t n_fixed_parts= max_part_bit(found_part);
5099
if (n_fixed_parts != keyinfo->key_parts &&
5100
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
5101
PREV_BITS(uint, keyinfo->key_parts))
5104
Not all parts are fixed. Produce bitmap of remaining bits and
5105
check if all of them are covered.
5107
sj_inside_out_scan= true;
5111
It's a confluent ref scan.
5113
That is, all found KEYUSE elements refer to IN-equalities,
5114
and there is really no ref access because there is no
5115
t.keypart0 = {bound expression}
5117
Calculate the cost of complete loose index scan.
5119
records= (double)s->table->file->stats.records;
5121
/* The cost is entire index scan cost (divided by 2) */
5122
best_time= s->table->file->index_only_read_time(key, records);
5124
/* Now figure how many different keys we will get */
5126
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
5127
records= records / rpc;
5134
Check if we found full key
5136
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
5139
max_key_part= UINT32_MAX;
5140
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
5142
tmp = prev_record_reads(join, idx, found_ref);
5148
{ /* We found a const key */
5150
ReuseRangeEstimateForRef-1:
5151
We get here if we've found a ref(const) (c_i are constants):
5152
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
5154
If range optimizer was able to construct a "range"
5155
access on this index, then its condition "quick_cond" was
5156
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
5157
from the range optimizer.
5159
Proof of (*): By properties of range and ref optimizers
5160
quick_cond will be equal or tighther than ref_const_cond.
5161
ref_const_cond already covers "smallest" possible interval -
5162
a singlepoint interval over all keyparts. Therefore,
5163
quick_cond is equivalent to ref_const_cond (if it was an
5164
empty interval we wouldn't have got here).
5166
if (table->quick_keys.is_set(key))
5167
records= (double) table->quick_rows[key];
5170
/* quick_range couldn't use key! */
5171
records= (double) s->records/rec;
5176
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
5177
{ /* Prefer longer keys */
5179
((double) s->records / (double) rec *
5181
((double) (table->s->max_key_length-keyinfo->key_length) /
5182
(double) table->s->max_key_length)));
5184
records=2.0; /* Can't be as good as a unique */
5187
ReuseRangeEstimateForRef-2: We get here if we could not reuse
5188
E(#rows) from range optimizer. Make another try:
5190
If range optimizer produced E(#rows) for a prefix of the ref
5191
access we're considering, and that E(#rows) is lower then our
5192
current estimate, make an adjustment. The criteria of when we
5193
can make an adjustment is a special case of the criteria used
5194
in ReuseRangeEstimateForRef-3.
5196
if (table->quick_keys.is_set(key) &&
5197
const_part & (1 << table->quick_key_parts[key]) &&
5198
table->quick_n_ranges[key] == 1 &&
5199
records > (double) table->quick_rows[key])
5201
records= (double) table->quick_rows[key];
5204
/* Limit the number of matched rows */
5206
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5207
if (table->covering_keys.is_set(key))
5209
/* we can use only index tree */
5210
tmp= record_count * table->file->index_only_read_time(key, tmp);
5213
tmp= record_count*cmin(tmp,s->worst_seeks);
5219
Use as much key-parts as possible and a uniq key is better
5220
than a not unique key
5221
Set tmp to (previous record count) * (records / combination)
5223
if ((found_part & 1) &&
5224
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
5225
found_part == PREV_BITS(uint,keyinfo->key_parts)))
5227
max_key_part= max_part_bit(found_part);
5229
ReuseRangeEstimateForRef-3:
5230
We're now considering a ref[or_null] access via
5231
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
5232
(same-as-above but with one cond replaced
5233
with "t.keypart_i IS NULL")] (**)
5235
Try re-using E(#rows) from "range" optimizer:
5236
We can do so if "range" optimizer used the same intervals as
5237
in (**). The intervals used by range optimizer may be not
5238
available at this point (as "range" access might have choosen to
5239
create quick select over another index), so we can't compare
5240
them to (**). We'll make indirect judgements instead.
5241
The sufficient conditions for re-use are:
5242
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
5243
this is not satisfied we have no way to know which ranges
5244
will be actually scanned by 'ref' until we execute the
5246
(C2) max #key parts in 'range' access == K == max_key_part (this
5247
is apparently a necessary requirement)
5249
We also have a property that "range optimizer produces equal or
5250
tighter set of scan intervals than ref(const) optimizer". Each
5251
of the intervals in (**) are "tightest possible" intervals when
5252
one limits itself to using keyparts 1..K (which we do in #2).
5253
From here it follows that range access used either one, or
5254
both of the (I1) and (I2) intervals:
5256
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
5257
(same-as-above but with one cond replaced
5258
with "t.keypart_i IS NULL") (I2)
5260
The remaining part is to exclude the situation where range
5261
optimizer used one interval while we're considering
5262
ref-or-null and looking for estimate for two intervals. This
5263
is done by last limitation:
5265
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
5267
if (table->quick_keys.is_set(key) && !found_ref && //(C1)
5268
table->quick_key_parts[key] == max_key_part && //(C2)
5269
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
5271
tmp= records= (double) table->quick_rows[key];
5275
/* Check if we have statistic about the distribution */
5276
if ((records= keyinfo->rec_per_key[max_key_part-1]))
5279
Fix for the case where the index statistics is too
5281
(1) We're considering ref(const) and there is quick select
5283
(2) and that quick select uses more keyparts (i.e. it will
5284
scan equal/smaller interval then this ref(const))
5285
(3) and E(#rows) for quick select is higher then our
5288
We'll use E(#rows) from quick select.
5290
Q: Why do we choose to use 'ref'? Won't quick select be
5291
cheaper in some cases ?
5292
TODO: figure this out and adjust the plan choice if needed.
5294
if (!found_ref && table->quick_keys.is_set(key) && // (1)
5295
table->quick_key_parts[key] > max_key_part && // (2)
5296
records < (double)table->quick_rows[key]) // (3)
5297
records= (double)table->quick_rows[key];
5304
Assume that the first key part matches 1% of the file
5305
and that the whole key matches 10 (duplicates) or 1
5307
Assume also that more key matches proportionally more
5309
This gives the formula:
5310
records = (x * (b-a) + a*c-b)/(c-1)
5312
b = records matched by whole key
5313
a = records matched by first key part (1% of all records?)
5314
c = number of key parts in key
5315
x = used key parts (1 <= x <= c)
5318
if (!(rec_per_key=(double)
5319
keyinfo->rec_per_key[keyinfo->key_parts-1]))
5320
rec_per_key=(double) s->records/rec+1;
5324
else if (rec_per_key/(double) s->records >= 0.01)
5328
double a=s->records*0.01;
5329
if (keyinfo->key_parts > 1)
5330
tmp= (max_key_part * (rec_per_key - a) +
5331
a*keyinfo->key_parts - rec_per_key)/
5332
(keyinfo->key_parts-1);
5335
set_if_bigger(tmp,1.0);
5337
records = (uint32_t) tmp;
5340
if (ref_or_null_part)
5342
/* We need to do two key searches to find key */
5348
ReuseRangeEstimateForRef-4: We get here if we could not reuse
5349
E(#rows) from range optimizer. Make another try:
5351
If range optimizer produced E(#rows) for a prefix of the ref
5352
access we're considering, and that E(#rows) is lower then our
5353
current estimate, make the adjustment.
5355
The decision whether we can re-use the estimate from the range
5356
optimizer is the same as in ReuseRangeEstimateForRef-3,
5357
applied to first table->quick_key_parts[key] key parts.
5359
if (table->quick_keys.is_set(key) &&
5360
table->quick_key_parts[key] <= max_key_part &&
5361
const_part & (1 << table->quick_key_parts[key]) &&
5362
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
5363
const_part) ? 1 : 0) &&
5364
records > (double) table->quick_rows[key])
5366
tmp= records= (double) table->quick_rows[key];
5370
/* Limit the number of matched rows */
5371
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5372
if (table->covering_keys.is_set(key))
5374
/* we can use only index tree */
5375
tmp= record_count * table->file->index_only_read_time(key, tmp);
5378
tmp= record_count * cmin(tmp,s->worst_seeks);
5381
tmp= best_time; // Do nothing
5384
if (sj_inside_out_scan && !start_key)
5392
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
5394
best_time= tmp + records/(double) TIME_FOR_COMPARE;
5396
best_records= records;
5397
best_key= start_key;
5398
best_max_key_part= max_key_part;
5399
best_ref_depends_map= found_ref;
5400
best_is_sj_inside_out= sj_inside_out_scan;
5403
records= best_records;
5407
Don't test table scan if it can't be better.
5408
Prefer key lookup if we would use the same key for scanning.
5410
Don't do a table scan on InnoDB tables, if we can read the used
5411
parts of the row from any of the used index.
5412
This is because table scans uses index and we would not win
5413
anything by using a table scan.
5415
A word for word translation of the below if-statement in sergefp's
5416
understanding: we check if we should use table scan if:
5417
(1) The found 'ref' access produces more records than a table scan
5418
(or index scan, or quick select), or 'ref' is more expensive than
5420
(2) This doesn't hold: the best way to perform table scan is to to perform
5421
'range' access using index IDX, and the best way to perform 'ref'
5422
access is to use the same index IDX, with the same or more key parts.
5423
(note: it is not clear how this rule is/should be extended to
5424
index_merge quick selects)
5425
(3) See above note about InnoDB.
5426
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
5427
path, but there is no quick select)
5428
If the condition in the above brackets holds, then the only possible
5429
"table scan" access method is ALL/index (there is no quick select).
5430
Since we have a 'ref' access path, and FORCE INDEX instructs us to
5431
choose it over ALL/index, there is no need to consider a full table
5434
if ((records >= s->found_records || best > s->read_time) && // (1)
5435
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
5436
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
5437
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
5438
! s->table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
5439
!(s->table->force_index && best_key && !s->quick)) // (4)
5440
{ // Check full join
5441
ha_rows rnd_records= s->found_records;
5443
If there is a filtering condition on the table (i.e. ref analyzer found
5444
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
5445
preceding this table in the join order we're now considering), then
5446
assume that 25% of the rows will be filtered out by this condition.
5448
This heuristic is supposed to force tables used in exprZ to be before
5449
this table in join order.
5451
if (found_constraint)
5452
rnd_records-= rnd_records/4;
5455
If applicable, get a more accurate estimate. Don't use the two
5458
if (s->table->quick_condition_rows != s->found_records)
5459
rnd_records= s->table->quick_condition_rows;
5462
Range optimizer never proposes a RANGE if it isn't better
5463
than FULL: so if RANGE is present, it's always preferred to FULL.
5464
Here we estimate its cost.
5470
- read record range through 'quick'
5471
- skip rows which does not satisfy WHERE constraints
5473
We take into account possible use of join cache for ALL/index
5474
access (see first else-branch below), but we don't take it into
5475
account here for range/index_merge access. Find out why this is so.
5478
(s->quick->read_time +
5479
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
5483
/* Estimate cost of reading table. */
5484
tmp= s->table->file->scan_time();
5485
if (s->table->map & join->outer_join) // Can't use join cache
5488
For each record we have to:
5489
- read the whole table record
5490
- skip rows which does not satisfy join condition
5494
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
5498
/* We read the table as many times as join buffer becomes full. */
5499
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
5501
(double) session->variables.join_buff_size));
5503
We don't make full cartesian product between rows in the scanned
5504
table and existing records because we skip all rows from the
5505
scanned table, which does not satisfy join condition when
5506
we read the table (see flush_cached_records for details). Here we
5507
take into account cost to read and skip these records.
5509
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
5514
We estimate the cost of evaluating WHERE clause for found records
5515
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
5516
tmp give us total cost of using Table SCAN
5518
if (best == DBL_MAX ||
5519
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
5520
best + record_count/(double) TIME_FOR_COMPARE*records))
5523
If the table has a range (s->quick is set) make_join_select()
5524
will ensure that this will be used
5527
records= rows2double(rnd_records);
5529
/* range/index_merge/ALL/index access method are "independent", so: */
5530
best_ref_depends_map= 0;
5531
best_is_sj_inside_out= false;
5535
/* Update the cost information for the current partial plan */
5536
join->positions[idx].records_read= records;
5537
join->positions[idx].read_time= best;
5538
join->positions[idx].key= best_key;
5539
join->positions[idx].table= s;
5540
join->positions[idx].ref_depend_map= best_ref_depends_map;
5541
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
5544
idx == join->const_tables &&
5545
s->table == join->sort_by_table &&
5546
join->unit->select_limit_cnt >= records)
5547
join->sort_by_table= (Table*) 1; // Must use temporary table
5554
Selects and invokes a search strategy for an optimal query plan.
5556
The function checks user-configurable parameters that control the search
5557
strategy for an optimal plan, selects the search method and then invokes
5558
it. Each specific optimization procedure stores the final optimal plan in
5559
the array 'join->best_positions', and the cost of the plan in
5562
@param join pointer to the structure providing all context info for
5564
@param join_tables set of the tables in the query
5567
'MAX_TABLES+2' denotes the old implementation of find_best before
5568
the greedy version. Will be removed when greedy_search is approved.
5577
choose_plan(JOIN *join, table_map join_tables)
5579
uint32_t search_depth= join->session->variables.optimizer_search_depth;
5580
uint32_t prune_level= join->session->variables.optimizer_prune_level;
5581
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
5583
join->cur_embedding_map= 0;
5584
reset_nj_counters(join->join_list);
5586
if (SELECT_STRAIGHT_JOIN option is set)
5587
reorder tables so dependent tables come after tables they depend
5588
on, otherwise keep tables in the order they were specified in the query
5590
Apply heuristic: pre-sort all access plans with respect to the number of
5593
my_qsort(join->best_ref + join->const_tables,
5594
join->tables - join->const_tables, sizeof(JOIN_TAB*),
5595
straight_join ? join_tab_cmp_straight : join_tab_cmp);
5596
join->cur_emb_sj_nests= 0;
5599
optimize_straight_join(join, join_tables);
5603
if (search_depth == MAX_TABLES+2)
5605
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
5606
the greedy version. Will be removed when greedy_search is approved.
5608
join->best_read= DBL_MAX;
5609
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
5614
if (search_depth == 0)
5615
/* Automatically determine a reasonable value for 'search_depth' */
5616
search_depth= determine_search_depth(join);
5617
if (greedy_search(join, join_tables, search_depth, prune_level))
5623
Store the cost of this query into a user variable
5624
Don't update last_query_cost for statements that are not "flat joins" :
5625
i.e. they have subqueries, unions or call stored procedures.
5626
TODO: calculate a correct cost for a query with subqueries and UNIONs.
5628
if (join->session->lex->is_single_level_stmt())
5629
join->session->status_var.last_query_cost= join->best_read;
5635
Compare two JOIN_TAB objects based on the number of accessed records.
5637
@param ptr1 pointer to first JOIN_TAB object
5638
@param ptr2 pointer to second JOIN_TAB object
800
5641
The order relation implemented by join_tab_cmp() is not transitive,
5693
Heuristic procedure to automatically guess a reasonable degree of
5694
exhaustiveness for the greedy search procedure.
5696
The procedure estimates the optimization time and selects a search depth
5697
big enough to result in a near-optimal QEP, that doesn't take too long to
5698
find. If the number of tables in the query exceeds some constant, then
5699
search_depth is set to this constant.
5701
@param join pointer to the structure providing all context info for
5705
This is an extremely simplistic implementation that serves as a stub for a
5706
more advanced analysis of the join. Ideally the search depth should be
5707
determined by learning from previous query optimizations, because it will
5708
depend on the CPU power (and other factors).
5711
this value should be determined dynamically, based on statistics:
5712
uint32_t max_tables_for_exhaustive_opt= 7;
5715
this value could be determined by some mapping of the form:
5716
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5719
A positive integer that specifies the search depth (and thus the
5720
exhaustiveness) of the depth-first search algorithm used by
5725
determine_search_depth(JOIN *join)
5727
uint32_t table_count= join->tables - join->const_tables;
5728
uint32_t search_depth;
5729
/* TODO: this value should be determined dynamically, based on statistics: */
5730
uint32_t max_tables_for_exhaustive_opt= 7;
5732
if (table_count <= max_tables_for_exhaustive_opt)
5733
search_depth= table_count+1; // use exhaustive for small number of tables
5736
TODO: this value could be determined by some mapping of the form:
5737
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5739
search_depth= max_tables_for_exhaustive_opt; // use greedy search
5741
return search_depth;
5746
Select the best ways to access the tables in a query without reordering them.
5748
Find the best access paths for each query table and compute their costs
5749
according to their order in the array 'join->best_ref' (thus without
5750
reordering the join tables). The function calls sequentially
5751
'best_access_path' for each table in the query to select the best table
5752
access method. The final optimal plan is stored in the array
5753
'join->best_positions', and the corresponding cost in 'join->best_read'.
5755
@param join pointer to the structure providing all context info for
5757
@param join_tables set of the tables in the query
5760
This function can be applied to:
5761
- queries with STRAIGHT_JOIN
5762
- internally to compute the cost of an arbitrary QEP
5764
Thus 'optimize_straight_join' can be used at any stage of the query
5765
optimization process to finalize a QEP as it is.
5769
optimize_straight_join(JOIN *join, table_map join_tables)
5772
uint32_t idx= join->const_tables;
5773
double record_count= 1.0;
5774
double read_time= 0.0;
5776
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
5778
/* Find the best access method from 's' to the current partial plan */
5779
advance_sj_state(join_tables, s);
5780
best_access_path(join, s, join->session, join_tables, idx,
5781
record_count, read_time);
5782
/* compute the cost of the new plan extended with 's' */
5783
record_count*= join->positions[idx].records_read;
5784
read_time+= join->positions[idx].read_time;
5785
join_tables&= ~(s->table->map);
5789
read_time+= record_count / (double) TIME_FOR_COMPARE;
5790
if (join->sort_by_table &&
5791
join->sort_by_table != join->positions[join->const_tables].table->table)
5792
read_time+= record_count; // We have to make a temp table
5793
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
5794
join->best_read= read_time;
5799
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
5801
The search procedure uses a hybrid greedy/exhaustive search with controlled
5802
exhaustiveness. The search is performed in N = card(remaining_tables)
5803
steps. Each step evaluates how promising is each of the unoptimized tables,
5804
selects the most promising table, and extends the current partial QEP with
5805
that table. Currenly the most 'promising' table is the one with least
5806
expensive extension.\
5808
There are two extreme cases:
5809
-# When (card(remaining_tables) < search_depth), the estimate finds the
5810
best complete continuation of the partial QEP. This continuation can be
5811
used directly as a result of the search.
5812
-# When (search_depth == 1) the 'best_extension_by_limited_search'
5813
consideres the extension of the current QEP with each of the remaining
5816
All other cases are in-between these two extremes. Thus the parameter
5817
'search_depth' controlls the exhaustiveness of the search. The higher the
5818
value, the longer the optimizaton time and possibly the better the
5819
resulting plan. The lower the value, the fewer alternative plans are
5820
estimated, but the more likely to get a bad QEP.
5822
All intermediate and final results of the procedure are stored in 'join':
5823
- join->positions : modified for every partial QEP that is explored
5824
- join->best_positions: modified for the current best complete QEP
5825
- join->best_read : modified for the current best complete QEP
5826
- join->best_ref : might be partially reordered
5828
The final optimal plan is stored in 'join->best_positions', and its
5829
corresponding cost in 'join->best_read'.
5832
The following pseudocode describes the algorithm of 'greedy_search':
5835
procedure greedy_search
5836
input: remaining_tables
5841
(t, a) = best_extension(pplan, remaining_tables);
5842
pplan = concat(pplan, (t, a));
5843
remaining_tables = remaining_tables - t;
5844
} while (remaining_tables != {})
5849
where 'best_extension' is a placeholder for a procedure that selects the
5850
most "promising" of all tables in 'remaining_tables'.
5851
Currently this estimate is performed by calling
5852
'best_extension_by_limited_search' to evaluate all extensions of the
5853
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
5854
mainly depends on that of 'best_extension_by_limited_search'.
5857
If 'best_extension()' == 'best_extension_by_limited_search()', then the
5858
worst-case complexity of this algorithm is <=
5859
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
5860
complexity of greedy_search is O(N!).
5863
In the future, 'greedy_search' might be extended to support other
5864
implementations of 'best_extension', e.g. some simpler quadratic procedure.
5866
@param join pointer to the structure providing all context info
5868
@param remaining_tables set of tables not included into the partial plan yet
5869
@param search_depth controlls the exhaustiveness of the search
5870
@param prune_level the pruning heuristics that should be applied during
5880
greedy_search(JOIN *join,
5881
table_map remaining_tables,
5882
uint32_t search_depth,
5883
uint32_t prune_level)
5885
double record_count= 1.0;
5886
double read_time= 0.0;
5887
uint32_t idx= join->const_tables; // index into 'join->best_ref'
5889
uint32_t size_remain; // cardinality of remaining_tables
5891
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
5893
/* number of tables that remain to be optimized */
5894
size_remain= my_count_bits(remaining_tables);
5897
/* Find the extension of the current QEP with the lowest cost */
5898
join->best_read= DBL_MAX;
5899
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
5900
read_time, search_depth, prune_level))
5903
if (size_remain <= search_depth)
5906
'join->best_positions' contains a complete optimal extension of the
5907
current partial QEP.
5912
/* select the first table in the optimal extension as most promising */
5913
best_pos= join->best_positions[idx];
5914
best_table= best_pos.table;
5916
Each subsequent loop of 'best_extension_by_limited_search' uses
5917
'join->positions' for cost estimates, therefore we have to update its
5920
join->positions[idx]= best_pos;
5922
/* find the position of 'best_table' in 'join->best_ref' */
5924
JOIN_TAB *pos= join->best_ref[best_idx];
5925
while (pos && best_table != pos)
5926
pos= join->best_ref[++best_idx];
5927
assert((pos != NULL)); // should always find 'best_table'
5928
/* move 'best_table' at the first free position in the array of joins */
5929
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
5931
/* compute the cost of the new plan extended with 'best_table' */
5932
record_count*= join->positions[idx].records_read;
5933
read_time+= join->positions[idx].read_time;
5935
remaining_tables&= ~(best_table->table->map);
5943
Find a good, possibly optimal, query execution plan (QEP) by a possibly
5946
The procedure searches for the optimal ordering of the query tables in set
5947
'remaining_tables' of size N, and the corresponding optimal access paths to
5948
each table. The choice of a table order and an access path for each table
5949
constitutes a query execution plan (QEP) that fully specifies how to
5952
The maximal size of the found plan is controlled by the parameter
5953
'search_depth'. When search_depth == N, the resulting plan is complete and
5954
can be used directly as a QEP. If search_depth < N, the found plan consists
5955
of only some of the query tables. Such "partial" optimal plans are useful
5956
only as input to query optimization procedures, and cannot be used directly
5959
The algorithm begins with an empty partial plan stored in 'join->positions'
5960
and a set of N tables - 'remaining_tables'. Each step of the algorithm
5961
evaluates the cost of the partial plan extended by all access plans for
5962
each of the relations in 'remaining_tables', expands the current partial
5963
plan with the access plan that results in lowest cost of the expanded
5964
partial plan, and removes the corresponding relation from
5965
'remaining_tables'. The algorithm continues until it either constructs a
5966
complete optimal plan, or constructs an optimal plartial plan with size =
5969
The final optimal plan is stored in 'join->best_positions'. The
5970
corresponding cost of the optimal plan is in 'join->best_read'.
5973
The procedure uses a recursive depth-first search where the depth of the
5974
recursion (and thus the exhaustiveness of the search) is controlled by the
5975
parameter 'search_depth'.
5978
The pseudocode below describes the algorithm of
5979
'best_extension_by_limited_search'. The worst-case complexity of this
5980
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
5981
the complexity of greedy_search is O(N!).
5984
procedure best_extension_by_limited_search(
5985
pplan in, // in, partial plan of tables-joined-so-far
5986
pplan_cost, // in, cost of pplan
5987
remaining_tables, // in, set of tables not referenced in pplan
5988
best_plan_so_far, // in/out, best plan found so far
5989
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5990
search_depth) // in, maximum size of the plans being considered
5992
for each table T from remaining_tables
5994
// Calculate the cost of using table T as above
5995
cost = complex-series-of-calculations;
5997
// Add the cost to the cost so far.
6000
if (pplan_cost >= best_plan_so_far_cost)
6001
// pplan_cost already too great, stop search
6004
pplan= expand pplan by best_access_method;
6005
remaining_tables= remaining_tables - table T;
6006
if (remaining_tables is not an empty set
6010
best_extension_by_limited_search(pplan, pplan_cost,
6013
best_plan_so_far_cost,
6018
best_plan_so_far_cost= pplan_cost;
6019
best_plan_so_far= pplan;
6026
When 'best_extension_by_limited_search' is called for the first time,
6027
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
6028
The actual implementation provides a way to optionally use pruning
6029
heuristic (controlled by the parameter 'prune_level') to reduce the search
6030
space by skipping some partial plans.
6033
The parameter 'search_depth' provides control over the recursion
6034
depth, and thus the size of the resulting optimal plan.
6036
@param join pointer to the structure providing all context info
6038
@param remaining_tables set of tables not included into the partial plan yet
6039
@param idx length of the partial QEP in 'join->positions';
6040
since a depth-first search is used, also corresponds
6041
to the current depth of the search tree;
6042
also an index in the array 'join->best_ref';
6043
@param record_count estimate for the number of records returned by the
6045
@param read_time the cost of the best partial plan
6046
@param search_depth maximum depth of the recursion and thus size of the
6048
(0 < search_depth <= join->tables+1).
6049
@param prune_level pruning heuristics that should be applied during
6051
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
6060
best_extension_by_limited_search(JOIN *join,
6061
table_map remaining_tables,
6063
double record_count,
6065
uint32_t search_depth,
6066
uint32_t prune_level)
6068
Session *session= join->session;
6069
if (session->killed) // Abort
6073
'join' is a partial plan with lower cost than the best plan so far,
6074
so continue expanding it further with the tables in 'remaining_tables'.
6077
double best_record_count= DBL_MAX;
6078
double best_read_time= DBL_MAX;
6080
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
6082
table_map real_table_bit= s->table->map;
6083
if ((remaining_tables & real_table_bit) &&
6084
!(remaining_tables & s->dependent) &&
6085
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6087
double current_record_count, current_read_time;
6088
advance_sj_state(remaining_tables, s);
6091
psergey-insideout-todo:
6092
when best_access_path() detects it could do an InsideOut scan or
6093
some other scan, have it return an insideout scan and a flag that
6094
requests to "fork" this loop iteration. (Q: how does that behave
6095
when the depth is insufficient??)
6097
/* Find the best access method from 's' to the current partial plan */
6098
best_access_path(join, s, session, remaining_tables, idx,
6099
record_count, read_time);
6100
/* Compute the cost of extending the plan with 's' */
6101
current_record_count= record_count * join->positions[idx].records_read;
6102
current_read_time= read_time + join->positions[idx].read_time;
6104
/* Expand only partial plans with lower cost than the best QEP so far */
6105
if ((current_read_time +
6106
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
6108
restore_prev_nj_state(s);
6109
restore_prev_sj_state(remaining_tables, s);
6114
Prune some less promising partial plans. This heuristic may miss
6115
the optimal QEPs, thus it results in a non-exhaustive search.
6117
if (prune_level == 1)
6119
if (best_record_count > current_record_count ||
6120
best_read_time > current_read_time ||
6121
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
6123
if (best_record_count >= current_record_count &&
6124
best_read_time >= current_read_time &&
6125
/* TODO: What is the reasoning behind this condition? */
6126
(!(s->key_dependent & remaining_tables) ||
6127
join->positions[idx].records_read < 2.0))
6129
best_record_count= current_record_count;
6130
best_read_time= current_read_time;
6135
restore_prev_nj_state(s);
6136
restore_prev_sj_state(remaining_tables, s);
6141
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
6142
{ /* Recursively expand the current partial plan */
6143
std::swap(join->best_ref[idx], *pos);
6144
if (best_extension_by_limited_search(join,
6145
remaining_tables & ~real_table_bit,
6147
current_record_count,
6152
std::swap(join->best_ref[idx], *pos);
6156
'join' is either the best partial QEP with 'search_depth' relations,
6157
or the best complete QEP so far, whichever is smaller.
6159
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
6160
if (join->sort_by_table &&
6161
join->sort_by_table !=
6162
join->positions[join->const_tables].table->table)
6163
/* We have to make a temp table */
6164
current_read_time+= current_record_count;
6165
if ((search_depth == 1) || (current_read_time < join->best_read))
6167
memcpy(join->best_positions, join->positions,
6168
sizeof(POSITION) * (idx + 1));
6169
join->best_read= current_read_time - 0.001;
6172
restore_prev_nj_state(s);
6173
restore_prev_sj_state(remaining_tables, s);
6182
- TODO: this function is here only temporarily until 'greedy_search' is
6183
tested and accepted.
6190
find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count,
6193
Session *session= join->session;
6194
if (session->killed)
6198
read_time+=record_count/(double) TIME_FOR_COMPARE;
6199
if (join->sort_by_table &&
6200
join->sort_by_table !=
6201
join->positions[join->const_tables].table->table)
6202
read_time+=record_count; // We have to make a temp table
6203
if (read_time < join->best_read)
6205
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
6206
join->best_read= read_time - 0.001;
6210
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
6211
return(false); /* Found better before */
6214
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
6215
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
6217
table_map real_table_bit=s->table->map;
6218
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
6219
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6221
double records, best;
6222
advance_sj_state(rest_tables, s);
6223
best_access_path(join, s, session, rest_tables, idx, record_count,
6225
records= join->positions[idx].records_read;
6226
best= join->positions[idx].read_time;
6228
Go to the next level only if there hasn't been a better key on
6229
this level! This will cut down the search for a lot simple cases!
6231
double current_record_count=record_count*records;
6232
double current_read_time=read_time+best;
6233
if (best_record_count > current_record_count ||
6234
best_read_time > current_read_time ||
6235
(idx == join->const_tables && s->table == join->sort_by_table))
6237
if (best_record_count >= current_record_count &&
6238
best_read_time >= current_read_time &&
6239
(!(s->key_dependent & rest_tables) || records < 2.0))
6241
best_record_count=current_record_count;
6242
best_read_time=current_read_time;
6244
std::swap(join->best_ref[idx], *pos);
6245
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
6246
current_record_count,current_read_time))
6248
std::swap(join->best_ref[idx], *pos);
6250
restore_prev_nj_state(s);
6251
restore_prev_sj_state(rest_tables, s);
6252
if (join->select_options & SELECT_STRAIGHT_JOIN)
6253
break; // Don't test all combinations
849
6261
Find how much space the prevous read not const tables takes in cache.
851
void calc_used_field_length(Session *, JoinTable *join_tab)
6264
static void calc_used_field_length(Session *, JOIN_TAB *join_tab)
853
6266
uint32_t null_fields,blobs,fields,rec_length;
854
6267
Field **f_ptr,*field;
6268
MY_BITMAP *read_set= join_tab->table->read_set;;
856
6270
null_fields= blobs= fields= rec_length=0;
857
for (f_ptr=join_tab->table->getFields() ; (field= *f_ptr) ; f_ptr++)
6271
for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++)
859
if (field->isReadSet())
6273
if (bitmap_is_set(read_set, field->field_index))
861
6275
uint32_t flags=field->flags;
863
6277
rec_length+=field->pack_length();
864
6278
if (flags & BLOB_FLAG)
866
6280
if (!(flags & NOT_NULL_FLAG))
870
6284
if (null_fields)
873
6287
rec_length+=sizeof(bool);
876
uint32_t blob_length=(uint32_t) (join_tab->table->cursor->stats.mean_rec_length-
877
(join_tab->table->getRecordLength()- rec_length));
878
rec_length+= max((uint32_t)4,blob_length);
880
join_tab->used_fields= fields;
881
join_tab->used_fieldlength= rec_length;
882
join_tab->used_blobs= blobs;
885
StoredKey *get_store_key(Session *session,
886
optimizer::KeyUse *keyuse,
887
table_map used_tables,
888
KeyPartInfo *key_part,
889
unsigned char *key_buff,
892
Item_ref *key_use_val= static_cast<Item_ref *>(keyuse->getVal());
893
if (! ((~used_tables) & keyuse->getUsedTables())) // if const item
6290
uint32_t blob_length=(uint32_t) (join_tab->table->file->stats.mean_rec_length-
6291
(join_tab->table->getRecordLength()- rec_length));
6292
rec_length+=(uint32_t) cmax((uint32_t)4,blob_length);
6294
join_tab->used_fields=fields;
6295
join_tab->used_fieldlength=rec_length;
6296
join_tab->used_blobs=blobs;
6301
cache_record_length(JOIN *join,uint32_t idx)
6304
JOIN_TAB **pos,**end;
6305
Session *session=join->session;
6307
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
6311
JOIN_TAB *join_tab= *pos;
6312
if (!join_tab->used_fieldlength) /* Not calced yet */
6313
calc_used_field_length(session, join_tab);
6314
length+=join_tab->used_fieldlength;
6321
Get the number of different row combinations for subset of partial join
6325
join The join structure
6326
idx Number of tables in the partial join order (i.e. the
6327
partial join order is in join->positions[0..idx-1])
6328
found_ref Bitmap of tables for which we need to find # of distinct
6332
Given a partial join order (in join->positions[0..idx-1]) and a subset of
6333
tables within that join order (specified in found_ref), find out how many
6334
distinct row combinations of subset tables will be in the result of the
6337
This is used as follows: Suppose we have a table accessed with a ref-based
6338
method. The ref access depends on current rows of tables in found_ref.
6339
We want to count # of different ref accesses. We assume two ref accesses
6340
will be different if at least one of access parameters is different.
6341
Example: consider a query
6343
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
6346
t1, ref access on t1.key=c1
6347
t2, ref access on t2.key=c2
6348
t3, ref access on t3.key=t1.field
6350
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
6351
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
6352
For t3: n_ref_scans = records_read(t1)*records_read(t2)
6353
n_distinct_ref_scans = #records_read(t1)
6355
The reason for having this function (at least the latest version of it)
6356
is that we need to account for buffering in join execution.
6358
An edge-case example: if we have a non-first table in join accessed via
6359
ref(const) or ref(param) where there is a small number of different
6360
values of param, then the access will likely hit the disk cache and will
6361
not require any disk seeks.
6363
The proper solution would be to assume an LRU disk cache of some size,
6364
calculate probability of cache hits, etc. For now we just count
6365
identical ref accesses as one.
6368
Expected number of row combinations
6372
prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
6375
POSITION *pos_end= join->positions - 1;
6376
for (POSITION *pos= join->positions + idx - 1; pos != pos_end; pos--)
6378
if (pos->table->table->map & found_ref)
6380
found_ref|= pos->ref_depend_map;
6382
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
6383
with no matching row we will get position[t2].records_read==0.
6384
Actually the size of output is one null-complemented row, therefore
6385
we will use value of 1 whenever we get records_read==0.
6388
- the above case can't occur if inner part of outer join has more
6389
than one table: table with no matches will not be marked as const.
6391
- Ideally we should add 1 to records_read for every possible null-
6392
complemented row. We're not doing it because: 1. it will require
6393
non-trivial code and add overhead. 2. The value of records_read
6394
is an inprecise estimate and adding 1 (or, in the worst case,
6395
#max_nested_outer_joins=64-1) will not make it any more precise.
6397
if (pos->records_read > DBL_EPSILON)
6398
found*= pos->records_read;
6406
Set up join struct according to best position.
6410
get_best_combination(JOIN *join)
6413
table_map used_tables;
6414
JOIN_TAB *join_tab,*j;
6416
uint32_t table_count;
6417
Session *session=join->session;
6419
table_count=join->tables;
6420
if (!(join->join_tab=join_tab=
6421
(JOIN_TAB*) session->alloc(sizeof(JOIN_TAB)*table_count)))
6426
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
6427
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
6430
*j= *join->best_positions[tablenr].table;
6431
form=join->table[tablenr]=j->table;
6432
used_tables|= form->map;
6433
form->reginfo.join_tab=j;
6434
if (!*j->on_expr_ref)
6435
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
6436
if (j->type == JT_CONST)
6437
continue; // Handled in make_join_stat..
6442
if (j->type == JT_SYSTEM)
6444
if (j->keys.is_clear_all() || !(keyuse= join->best_positions[tablenr].key))
6447
if (tablenr != join->const_tables)
6450
else if (create_ref_for_key(join, j, keyuse, used_tables))
6451
return(true); // Something went wrong
6454
for (i=0 ; i < table_count ; i++)
6455
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
6456
update_depend_map(join);
6461
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
6462
table_map used_tables)
6464
KEYUSE *keyuse=org_keyuse;
6465
Session *session= join->session;
6466
uint32_t keyparts,length,key;
6470
/* Use best key from find_best */
6473
keyinfo=table->key_info+key;
6477
uint32_t found_part_ref_or_null= 0;
6479
Calculate length for the used key
6480
Stop if there is a missing key part or when we find second key_part
6481
with KEY_OPTIMIZE_REF_OR_NULL
6485
if (!(~used_tables & keyuse->used_tables))
6487
if (keyparts == keyuse->keypart &&
6488
!(found_part_ref_or_null & keyuse->optimize))
6491
length+= keyinfo->key_part[keyuse->keypart].store_length;
6492
found_part_ref_or_null|= keyuse->optimize;
6496
} while (keyuse->table == table && keyuse->key == key);
6499
/* set up fieldref */
6500
keyinfo=table->key_info+key;
6501
j->ref.key_parts=keyparts;
6502
j->ref.key_length=length;
6503
j->ref.key=(int) key;
6504
if (!(j->ref.key_buff= (unsigned char*) session->calloc(ALIGN_SIZE(length)*2)) ||
6505
!(j->ref.key_copy= (store_key**) session->alloc((sizeof(store_key*) *
6507
!(j->ref.items= (Item**) session->alloc(sizeof(Item*)*keyparts)) ||
6508
!(j->ref.cond_guards= (bool**) session->alloc(sizeof(uint*)*keyparts)))
6512
j->ref.key_buff2=j->ref.key_buff+ALIGN_SIZE(length);
6514
j->ref.null_rejecting= 0;
6515
j->ref.disable_cache= false;
6518
store_key **ref_key= j->ref.key_copy;
6519
unsigned char *key_buff=j->ref.key_buff, *null_ref_key= 0;
6520
bool keyuse_uses_no_tables= true;
6523
for (i=0 ; i < keyparts ; keyuse++,i++)
6525
while (keyuse->keypart != i ||
6526
((~used_tables) & keyuse->used_tables))
6527
keyuse++; /* Skip other parts */
6529
uint32_t maybe_null= test(keyinfo->key_part[i].null_bit);
6530
j->ref.items[i]=keyuse->val; // Save for cond removal
6531
j->ref.cond_guards[i]= keyuse->cond_guard;
6532
if (keyuse->null_rejecting)
6533
j->ref.null_rejecting |= 1 << i;
6534
keyuse_uses_no_tables= keyuse_uses_no_tables && !keyuse->used_tables;
6535
if (!keyuse->used_tables &&
6536
!(join->select_options & SELECT_DESCRIBE))
6537
{ // Compare against constant
6538
store_key_item tmp(session, keyinfo->key_part[i].field,
6539
key_buff + maybe_null,
6540
maybe_null ? key_buff : 0,
6541
keyinfo->key_part[i].length, keyuse->val);
6542
if (session->is_fatal_error)
6547
*ref_key++= get_store_key(session,
6548
keyuse,join->const_table_map,
6549
&keyinfo->key_part[i],
6550
key_buff, maybe_null);
6552
Remember if we are going to use REF_OR_NULL
6553
But only if field _really_ can be null i.e. we force JT_REF
6554
instead of JT_REF_OR_NULL in case if field can't be null
6556
if ((keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL) && maybe_null)
6557
null_ref_key= key_buff;
6558
key_buff+=keyinfo->key_part[i].store_length;
6561
*ref_key=0; // end_marker
6562
if (j->type == JT_CONST)
6563
j->table->const_table= 1;
6564
else if (((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) != HA_NOSAME) ||
6565
keyparts != keyinfo->key_parts || null_ref_key)
6567
/* Must read with repeat */
6568
j->type= null_ref_key ? JT_REF_OR_NULL : JT_REF;
6569
j->ref.null_ref_key= null_ref_key;
6571
else if (keyuse_uses_no_tables)
6574
This happen if we are using a constant expression in the ON part
6576
SELECT * FROM a LEFT JOIN b ON b.key=30
6577
Here we should not mark the table as a 'const' as a field may
6578
have a 'normal' value or a NULL value.
6590
get_store_key(Session *session, KEYUSE *keyuse, table_map used_tables,
6591
KEY_PART_INFO *key_part, unsigned char *key_buff, uint32_t maybe_null)
6593
if (!((~used_tables) & keyuse->used_tables)) // if const item
895
6595
return new store_key_const_item(session,
896
6596
key_part->field,
897
6597
key_buff + maybe_null,
898
6598
maybe_null ? key_buff : 0,
899
6599
key_part->length,
902
else if (key_use_val->type() == Item::FIELD_ITEM ||
903
(key_use_val->type() == Item::REF_ITEM &&
904
key_use_val->ref_type() == Item_ref::OUTER_REF &&
905
(*(Item_ref**)((Item_ref*)key_use_val)->ref)->ref_type() == Item_ref::DIRECT_REF &&
906
key_use_val->real_item()->type() == Item::FIELD_ITEM))
6602
else if (keyuse->val->type() == Item::FIELD_ITEM ||
6603
(keyuse->val->type() == Item::REF_ITEM &&
6604
((Item_ref*)keyuse->val)->ref_type() == Item_ref::OUTER_REF &&
6605
(*(Item_ref**)((Item_ref*)keyuse->val)->ref)->ref_type() ==
6606
Item_ref::DIRECT_REF &&
6607
keyuse->val->real_item()->type() == Item::FIELD_ITEM))
908
6608
return new store_key_field(session,
909
6609
key_part->field,
910
6610
key_buff + maybe_null,
911
6611
maybe_null ? key_buff : 0,
912
6612
key_part->length,
913
((Item_field*) key_use_val->real_item())->field,
914
key_use_val->full_name());
6613
((Item_field*) keyuse->val->real_item())->field,
6614
keyuse->val->full_name());
916
6615
return new store_key_item(session,
917
6616
key_part->field,
918
6617
key_buff + maybe_null,
919
6618
maybe_null ? key_buff : 0,
920
6619
key_part->length,
6864
Fill in outer join related info for the execution plan structure.
6866
For each outer join operation left after simplification of the
6867
original query the function set up the following pointers in the linear
6868
structure join->join_tab representing the selected execution plan.
6869
The first inner table t0 for the operation is set to refer to the last
6870
inner table tk through the field t0->last_inner.
6871
Any inner table ti for the operation are set to refer to the first
6872
inner table ti->first_inner.
6873
The first inner table t0 for the operation is set to refer to the
6874
first inner table of the embedding outer join operation, if there is any,
6875
through the field t0->first_upper.
6876
The on expression for the outer join operation is attached to the
6877
corresponding first inner table through the field t0->on_expr_ref.
6878
Here ti are structures of the JOIN_TAB type.
6880
EXAMPLE. For the query:
6884
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
6885
ON (t1.a=t2.a AND t1.b=t3.b)
6889
given the execution plan with the table order t1,t2,t3,t4
6890
is selected, the following references will be set;
6891
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
6892
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
6893
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
6894
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
6896
@param join reference to the info fully describing the query
6899
The function assumes that the simplification procedure has been
6900
already applied to the join query (see simplify_joins).
6901
This function can be called only after the execution plan
6906
make_outerjoin_info(JOIN *join)
6908
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6910
JOIN_TAB *tab=join->join_tab+i;
6911
Table *table=tab->table;
6912
TableList *tbl= table->pos_in_table_list;
6913
TableList *embedding= tbl->embedding;
6915
if (tbl->outer_join)
6918
Table tab is the only one inner table for outer join.
6919
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
6920
is in the query above.)
6922
tab->last_inner= tab->first_inner= tab;
6923
tab->on_expr_ref= &tbl->on_expr;
6924
tab->cond_equal= tbl->cond_equal;
6926
tab->first_upper= embedding->nested_join->first_nested;
6928
for ( ; embedding ; embedding= embedding->embedding)
6930
/* Ignore sj-nests: */
6931
if (!embedding->on_expr)
6933
nested_join_st *nested_join= embedding->nested_join;
6934
if (!nested_join->counter_)
6937
Table tab is the first inner table for nested_join.
6938
Save reference to it in the nested join structure.
6940
nested_join->first_nested= tab;
6941
tab->on_expr_ref= &embedding->on_expr;
6942
tab->cond_equal= tbl->cond_equal;
6943
if (embedding->embedding)
6944
tab->first_upper= embedding->embedding->nested_join->first_nested;
6946
if (!tab->first_inner)
6947
tab->first_inner= nested_join->first_nested;
6948
if (++nested_join->counter_ < nested_join->join_list.elements)
6950
/* Table tab is the last inner table for nested join. */
6951
nested_join->first_nested->last_inner= tab;
6959
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
6961
Session *session= join->session;
6964
add_not_null_conds(join);
6965
table_map used_tables;
6966
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
6967
{ /* there may be a select without a cond. */
6968
if (join->tables > 1)
6969
cond->update_used_tables(); // Tablenr may have changed
6970
if (join->const_tables == join->tables &&
6971
session->lex->current_select->master_unit() ==
6972
&session->lex->unit) // not upper level SELECT
6973
join->const_table_map|=RAND_TABLE_BIT;
6974
{ // Check const tables
6976
make_cond_for_table(cond,
6977
join->const_table_map,
6979
for (JOIN_TAB *tab= join->join_tab+join->const_tables;
6980
tab < join->join_tab+join->tables ; tab++)
6982
if (*tab->on_expr_ref)
6984
JOIN_TAB *cond_tab= tab->first_inner;
6985
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
6986
join->const_table_map,
6990
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
6993
tmp->quick_fix_field();
6994
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
6995
new Item_cond_and(cond_tab->select_cond,
6997
if (!cond_tab->select_cond)
6999
cond_tab->select_cond->quick_fix_field();
7002
if (const_cond && !const_cond->val_int())
7004
return(1); // Impossible const condition
7008
used_tables=((select->const_tables=join->const_table_map) |
7009
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7010
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
7012
JOIN_TAB *tab=join->join_tab+i;
7014
first_inner is the X in queries like:
7015
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
7017
JOIN_TAB *first_inner_tab= tab->first_inner;
7018
table_map current_map= tab->table->map;
7019
bool use_quick_range=0;
7023
Following force including random expression in last table condition.
7024
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
7026
if (i == join->tables-1)
7027
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
7028
used_tables|=current_map;
7030
if (tab->type == JT_REF && tab->quick &&
7031
(uint32_t) tab->ref.key == tab->quick->index &&
7032
tab->ref.key_length < tab->quick->max_used_key_length)
7034
/* Range uses longer key; Use this instead of ref on key */
7039
tab->ref.key_parts=0; // Don't use ref key.
7040
join->best_positions[i].records_read= rows2double(tab->quick->records);
7042
We will use join cache here : prevent sorting of the first
7043
table only and sort at the end.
7045
if (i != join->const_tables && join->tables > join->const_tables + 1)
7051
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
7052
if (cond && !tmp && tab->quick)
7054
if (tab->type != JT_ALL)
7057
Don't use the quick method
7058
We come here in the case where we have 'key=constant' and
7059
the test is removed by make_cond_for_table()
7067
Hack to handle the case where we only refer to a table
7068
in the ON part of an OUTER JOIN. In this case we want the code
7069
below to check if we should use 'quick' instead.
7071
tmp= new Item_int((int64_t) 1,1); // Always true
7075
if (tmp || !cond || tab->type == JT_REF || tab->type == JT_REF_OR_NULL ||
7076
tab->type == JT_EQ_REF)
7078
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
7079
session->memdup((unsigned char*) select,
7082
return(1); // End of memory
7084
If tab is an inner table of an outer join operation,
7085
add a match guard to the pushed down predicate.
7086
The guard will turn the predicate on only after
7087
the first match for outer tables is encountered.
7092
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
7093
a cond, so neutralize the hack above.
7095
if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
7097
tab->select_cond=sel->cond=tmp;
7098
/* Push condition to storage engine if this is enabled
7099
and the condition is not guarded */
7100
tab->table->file->pushed_cond= NULL;
7101
if (session->variables.engine_condition_pushdown)
7104
make_cond_for_table(tmp, current_map, current_map, 0);
7107
/* Push condition to handler */
7108
if (!tab->table->file->cond_push(push_cond))
7109
tab->table->file->pushed_cond= push_cond;
7114
tab->select_cond= sel->cond= NULL;
7116
sel->head=tab->table;
7119
/* Use quick key read if it's a constant and it's not used
7121
if (tab->needed_reg.is_clear_all() && tab->type != JT_EQ_REF
7122
&& (tab->type != JT_REF || (uint32_t) tab->ref.key == tab->quick->index))
7124
sel->quick=tab->quick; // Use value from get_quick_...
7125
sel->quick_keys.clear_all();
7126
sel->needed_reg.clear_all();
7134
uint32_t ref_key=(uint32_t) sel->head->reginfo.join_tab->ref.key+1;
7135
if (i == join->const_tables && ref_key)
7137
if (!tab->const_keys.is_clear_all() &&
7138
tab->table->reginfo.impossible_range)
7141
else if (tab->type == JT_ALL && ! use_quick_range)
7143
if (!tab->const_keys.is_clear_all() &&
7144
tab->table->reginfo.impossible_range)
7145
return(1); // Impossible range
7147
We plan to scan all rows.
7148
Check again if we should use an index.
7149
We could have used an column from a previous table in
7150
the index if we are using limit and this is the first table
7153
if ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||
7154
(!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)))
7156
/* Join with outer join condition */
7157
COND *orig_cond=sel->cond;
7158
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
7161
We can't call sel->cond->fix_fields,
7162
as it will break tab->on_expr if it's AND condition
7163
(fix_fields currently removes extra AND/OR levels).
7164
Yet attributes of the just built condition are not needed.
7165
Thus we call sel->cond->quick_fix_field for safety.
7167
if (sel->cond && !sel->cond->fixed)
7168
sel->cond->quick_fix_field();
7170
if (sel->test_quick_select(session, tab->keys,
7171
used_tables & ~ current_map,
7172
(join->select_options &
7175
join->unit->select_limit_cnt), 0,
7179
Before reporting "Impossible WHERE" for the whole query
7180
we have to check isn't it only "impossible ON" instead
7182
sel->cond=orig_cond;
7183
if (!*tab->on_expr_ref ||
7184
sel->test_quick_select(session, tab->keys,
7185
used_tables & ~ current_map,
7186
(join->select_options &
7189
join->unit->select_limit_cnt),0,
7191
return(1); // Impossible WHERE
7194
sel->cond=orig_cond;
7196
/* Fix for EXPLAIN */
7198
join->best_positions[i].records_read= (double)sel->quick->records;
7202
sel->needed_reg=tab->needed_reg;
7203
sel->quick_keys.clear_all();
7205
if (!sel->quick_keys.is_subset(tab->checked_keys) ||
7206
!sel->needed_reg.is_subset(tab->checked_keys))
7208
tab->keys=sel->quick_keys;
7209
tab->keys.merge(sel->needed_reg);
7210
tab->use_quick= (!sel->needed_reg.is_clear_all() &&
7211
(select->quick_keys.is_clear_all() ||
7213
(select->quick->records >= 100L)))) ?
7215
sel->read_tables= used_tables & ~current_map;
7217
if (i != join->const_tables && tab->use_quick != 2)
7218
{ /* Read with cache */
7220
(tmp=make_cond_for_table(cond,
7221
join->const_table_map |
7225
tab->cache.select=(SQL_SELECT*)
7226
session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
7227
tab->cache.select->cond=tmp;
7228
tab->cache.select->read_tables=join->const_table_map;
7235
Push down conditions from all on expressions.
7236
Each of these conditions are guarded by a variable
7237
that turns if off just before null complemented row for
7238
outer joins is formed. Thus, the condition from an
7239
'on expression' are guaranteed not to be checked for
7240
the null complemented row.
7243
/* First push down constant conditions from on expressions */
7244
for (JOIN_TAB *join_tab= join->join_tab+join->const_tables;
7245
join_tab < join->join_tab+join->tables ; join_tab++)
7247
if (*join_tab->on_expr_ref)
7249
JOIN_TAB *cond_tab= join_tab->first_inner;
7250
tmp= make_cond_for_table(*join_tab->on_expr_ref,
7251
join->const_table_map,
7255
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
7258
tmp->quick_fix_field();
7259
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
7260
new Item_cond_and(cond_tab->select_cond,tmp);
7261
if (!cond_tab->select_cond)
7263
cond_tab->select_cond->quick_fix_field();
7267
/* Push down non-constant conditions from on expressions */
7268
JOIN_TAB *last_tab= tab;
7269
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
7272
Table tab is the last inner table of an outer join.
7273
An on expression is always attached to it.
7275
COND *on_expr= *first_inner_tab->on_expr_ref;
7277
table_map used_tables2= (join->const_table_map |
7278
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7279
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
7281
current_map= tab->table->map;
7282
used_tables2|= current_map;
7283
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
7287
JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
7289
First add the guards for match variables of
7290
all embedding outer join operations.
7292
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
7297
Now add the guard turning the predicate off for
7298
the null complemented row.
7300
tmp_cond= new Item_func_trig_cond(tmp_cond,
7304
tmp_cond->quick_fix_field();
7305
/* Add the predicate to other pushed down predicates */
7306
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
7307
new Item_cond_and(cond_tab->select_cond,
7309
if (!cond_tab->select_cond)
7311
cond_tab->select_cond->quick_fix_field();
7314
first_inner_tab= first_inner_tab->first_upper;
7323
Check if given expression uses only table fields covered by the given index
7326
uses_index_fields_only()
7327
item Expression to check
7328
tbl The table having the index
7329
keyno The index number
7330
other_tbls_ok true <=> Fields of other non-const tables are allowed
7333
Check if given expression only uses fields covered by index #keyno in the
7334
table tbl. The expression can use any fields in any other tables.
7336
The expression is guaranteed not to be AND or OR - those constructs are
7337
handled outside of this function.
7344
bool uses_index_fields_only(Item *item, Table *tbl, uint32_t keyno,
7347
if (item->const_item())
7351
Don't push down the triggered conditions. Nested outer joins execution
7352
code may need to evaluate a condition several times (both triggered and
7353
untriggered), and there is no way to put thi
7354
TODO: Consider cloning the triggered condition and using the copies for:
7355
1. push the first copy down, to have most restrictive index condition
7357
2. Put the second copy into tab->select_cond.
7359
if (item->type() == Item::FUNC_ITEM &&
7360
((Item_func*)item)->functype() == Item_func::TRIG_COND_FUNC)
7363
if (!(item->used_tables() & tbl->map))
7364
return other_tbls_ok;
7366
Item::Type item_type= item->type();
7367
switch (item_type) {
7368
case Item::FUNC_ITEM:
7370
/* This is a function, apply condition recursively to arguments */
7371
Item_func *item_func= (Item_func*)item;
7373
Item **item_end= (item_func->arguments()) + item_func->argument_count();
7374
for (child= item_func->arguments(); child != item_end; child++)
7376
if (!uses_index_fields_only(*child, tbl, keyno, other_tbls_ok))
7381
case Item::COND_ITEM:
7383
/* This is a function, apply condition recursively to arguments */
7384
List_iterator<Item> li(*((Item_cond*)item)->argument_list());
7386
while ((list_item=li++))
7388
if (!uses_index_fields_only(item, tbl, keyno, other_tbls_ok))
7393
case Item::FIELD_ITEM:
7395
Item_field *item_field= (Item_field*)item;
7396
if (item_field->field->table != tbl)
7398
return item_field->field->part_of_key.is_set(keyno);
7400
case Item::REF_ITEM:
7401
return uses_index_fields_only(item->real_item(), tbl, keyno,
7404
return false; /* Play it safe, don't push unknown non-const items */
1216
7409
#define ICP_COND_USES_INDEX_ONLY 10
1222
void JoinTable::cleanup()
1224
safe_delete(select);
7412
Get a part of the condition that can be checked using only index fields
7415
make_cond_for_index()
7416
cond The source condition
7417
table The table that is partially available
7418
keyno The index in the above table. Only fields covered by the index
7420
other_tbls_ok true <=> Fields of other non-const tables are allowed
7423
Get a part of the condition that can be checked when for the given table
7424
we have values only of fields covered by some index. The condition may
7425
refer to other tables, it is assumed that we have values of all of their
7429
make_cond_for_index(
7430
"cond(t1.field) AND cond(t2.key1) AND cond(t2.non_key) AND cond(t2.key2)",
7433
"cond(t1.field) AND cond(t2.key2)"
7436
Index condition, or NULL if no condition could be inferred.
7439
Item *make_cond_for_index(Item *cond, Table *table, uint32_t keyno,
7444
if (cond->type() == Item::COND_ITEM)
7446
uint32_t n_marked= 0;
7447
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7449
Item_cond_and *new_cond=new Item_cond_and;
7452
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7456
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7458
new_cond->argument_list()->push_back(fix);
7459
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7461
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7462
cond->marker= ICP_COND_USES_INDEX_ONLY;
7463
switch (new_cond->argument_list()->elements) {
7467
return new_cond->argument_list()->head();
7469
new_cond->quick_fix_field();
7475
Item_cond_or *new_cond=new Item_cond_or;
7478
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7482
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7485
new_cond->argument_list()->push_back(fix);
7486
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7488
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7489
cond->marker= ICP_COND_USES_INDEX_ONLY;
7490
new_cond->quick_fix_field();
7491
new_cond->top_level_item();
7496
if (!uses_index_fields_only(cond, table, keyno, other_tbls_ok))
7498
cond->marker= ICP_COND_USES_INDEX_ONLY;
7503
Item *make_cond_remainder(Item *cond, bool exclude_index)
7505
if (exclude_index && cond->marker == ICP_COND_USES_INDEX_ONLY)
7506
return 0; /* Already checked */
7508
if (cond->type() == Item::COND_ITEM)
7510
table_map tbl_map= 0;
7511
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7513
/* Create new top level AND item */
7514
Item_cond_and *new_cond=new Item_cond_and;
7517
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7521
Item *fix= make_cond_remainder(item, exclude_index);
7524
new_cond->argument_list()->push_back(fix);
7525
tbl_map |= fix->used_tables();
7528
switch (new_cond->argument_list()->elements) {
7532
return new_cond->argument_list()->head();
7534
new_cond->quick_fix_field();
7535
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7541
Item_cond_or *new_cond=new Item_cond_or;
7544
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7548
Item *fix= make_cond_remainder(item, false);
7551
new_cond->argument_list()->push_back(fix);
7552
tbl_map |= fix->used_tables();
7554
new_cond->quick_fix_field();
7555
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7556
new_cond->top_level_item();
7565
Try to extract and push the index condition
7569
tab A join tab that has tab->table->file and its condition
7571
keyno Index for which extract and push the condition
7572
other_tbls_ok true <=> Fields of other non-const tables are allowed
7575
Try to extract and push the index condition down to table handler
7578
static void push_index_cond(JOIN_TAB *tab, uint32_t keyno, bool other_tbls_ok)
7581
if (tab->table->file->index_flags(keyno, 0, 1) & HA_DO_INDEX_COND_PUSHDOWN &&
7582
tab->join->session->variables.engine_condition_pushdown)
7584
idx_cond= make_cond_for_index(tab->select_cond, tab->table, keyno,
7589
tab->pre_idx_push_select_cond= tab->select_cond;
7590
Item *idx_remainder_cond=
7591
tab->table->file->idx_cond_push(keyno, idx_cond);
7594
Disable eq_ref's "lookup cache" if we've pushed down an index
7596
TODO: This check happens to work on current ICP implementations, but
7597
there may exist a compliant implementation that will not work
7598
correctly with it. Sort this out when we stabilize the condition
7601
if (idx_remainder_cond != idx_cond)
7602
tab->ref.disable_cache= true;
7604
Item *row_cond= make_cond_remainder(tab->select_cond, true);
7608
if (!idx_remainder_cond)
7609
tab->select_cond= row_cond;
7612
tab->select_cond= new Item_cond_and(row_cond, idx_remainder_cond);
7613
tab->select_cond->quick_fix_field();
7614
((Item_cond_and*)tab->select_cond)->used_tables_cache=
7615
row_cond->used_tables() | idx_remainder_cond->used_tables();
7619
tab->select_cond= idx_remainder_cond;
7622
tab->select->cond= tab->select_cond;
7632
Determine if the set is already ordered for order_st BY, so it can
7633
disable join cache because it will change the ordering of the results.
7634
Code handles sort table that is at any location (not only first after
7635
the const tables) despite the fact that it's currently prohibited.
7636
We must disable join cache if the first non-const table alone is
7637
ordered. If there is a temp table the ordering is done as a last
7638
operation and doesn't prevent join cache usage.
7640
uint32_t make_join_orderinfo(JOIN *join)
7644
return join->tables;
7646
for (i=join->const_tables ; i < join->tables ; i++)
7648
JOIN_TAB *tab=join->join_tab+i;
7649
Table *table=tab->table;
7650
if ((table == join->sort_by_table &&
7651
(!join->order || join->skip_sort_order)) ||
7652
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
7662
Plan refinement stage: do various set ups for the executioner
7665
make_join_readinfo()
7666
join Join being processed
7667
options Join's options (checking for SELECT_DESCRIBE,
7668
SELECT_NO_JOIN_CACHE)
7669
no_jbuf_after Don't use join buffering after table with this number.
7672
Plan refinement stage: do various set ups for the executioner
7673
- set up use of join buffering
7674
- push index conditions
7675
- increment counters
7680
true - Out of memory
7684
make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
7687
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
7690
for (i=join->const_tables ; i < join->tables ; i++)
7692
JOIN_TAB *tab=join->join_tab+i;
7693
Table *table=tab->table;
7694
bool using_join_cache;
7695
tab->read_record.table= table;
7696
tab->read_record.file=table->file;
7697
tab->next_select=sub_select; /* normal select */
7699
TODO: don't always instruct first table's ref/range access method to
7700
produce sorted output.
7702
tab->sorted= sorted;
7703
sorted= 0; // only first must be sorted
7704
if (tab->insideout_match_tab)
7706
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
7711
switch (tab->type) {
7712
case JT_SYSTEM: // Only happens with left join
7713
table->status=STATUS_NO_RECORD;
7714
tab->read_first_record= join_read_system;
7715
tab->read_record.read_record= join_no_more_records;
7717
case JT_CONST: // Only happens with left join
7718
table->status=STATUS_NO_RECORD;
7719
tab->read_first_record= join_read_const;
7720
tab->read_record.read_record= join_no_more_records;
7721
if (table->covering_keys.is_set(tab->ref.key) &&
7725
table->file->extra(HA_EXTRA_KEYREAD);
7729
table->status=STATUS_NO_RECORD;
7732
delete tab->select->quick;
7733
tab->select->quick=0;
7737
tab->read_first_record= join_read_key;
7738
tab->read_record.read_record= join_no_more_records;
7739
if (table->covering_keys.is_set(tab->ref.key) &&
7743
table->file->extra(HA_EXTRA_KEYREAD);
7746
push_index_cond(tab, tab->ref.key, true);
7748
case JT_REF_OR_NULL:
7750
table->status=STATUS_NO_RECORD;
7753
delete tab->select->quick;
7754
tab->select->quick=0;
7758
if (table->covering_keys.is_set(tab->ref.key) &&
7762
table->file->extra(HA_EXTRA_KEYREAD);
7765
push_index_cond(tab, tab->ref.key, true);
7766
if (tab->type == JT_REF)
7768
tab->read_first_record= join_read_always_key;
7769
tab->read_record.read_record= tab->insideout_match_tab?
7770
join_read_next_same_diff : join_read_next_same;
7774
tab->read_first_record= join_read_always_key_or_null;
7775
tab->read_record.read_record= join_read_next_same_or_null;
7780
If previous table use cache
7781
If the incoming data set is already sorted don't use cache.
7783
table->status=STATUS_NO_RECORD;
7784
using_join_cache= false;
7785
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
7786
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
7787
!tab->insideout_match_tab)
7789
if ((options & SELECT_DESCRIBE) ||
7790
!join_init_cache(join->session,join->join_tab+join->const_tables,
7791
i-join->const_tables))
7793
using_join_cache= true;
7794
tab[-1].next_select=sub_select_cache; /* Patch previous */
7797
/* These init changes read_record */
7798
if (tab->use_quick == 2)
7800
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
7801
tab->read_first_record= join_init_quick_read_record;
7803
status_var_increment(join->session->status_var.select_range_check_count);
7807
tab->read_first_record= join_init_read_record;
7808
if (i == join->const_tables)
7810
if (tab->select && tab->select->quick)
7813
status_var_increment(join->session->status_var.select_range_count);
7817
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
7819
status_var_increment(join->session->status_var.select_scan_count);
7824
if (tab->select && tab->select->quick)
7827
status_var_increment(join->session->status_var.select_full_range_join_count);
7831
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
7833
status_var_increment(join->session->status_var.select_full_join_count);
7836
if (!table->no_keyread)
7838
if (tab->select && tab->select->quick &&
7839
tab->select->quick->index != MAX_KEY && //not index_merge
7840
table->covering_keys.is_set(tab->select->quick->index))
7843
table->file->extra(HA_EXTRA_KEYREAD);
7845
else if (!table->covering_keys.is_clear_all() &&
7846
!(tab->select && tab->select->quick))
7847
{ // Only read index tree
7848
if (!tab->insideout_match_tab)
7851
See bug #26447: "Using the clustered index for a table scan
7852
is always faster than using a secondary index".
7854
if (table->s->primary_key != MAX_KEY &&
7855
table->file->primary_key_is_clustered())
7856
tab->index= table->s->primary_key;
7858
tab->index= table->find_shortest_key(&table->covering_keys);
7860
tab->read_first_record= join_read_first;
7861
tab->type=JT_NEXT; // Read with index_first / index_next
7864
if (tab->select && tab->select->quick &&
7865
tab->select->quick->index != MAX_KEY && ! tab->table->key_read)
7866
push_index_cond(tab, tab->select->quick->index, !using_join_cache);
7870
break; /* purecov: deadcode */
7873
abort(); /* purecov: deadcode */
7876
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
7882
Give error if we some tables are done with a full join.
7884
This is used by multi_table_update and multi_table_delete when running
7887
@param join Join condition
7892
1 Error (full join used)
7895
bool error_if_full_join(JOIN *join)
7897
for (JOIN_TAB *tab=join->join_tab, *end=join->join_tab+join->tables;
7901
if (tab->type == JT_ALL && (!tab->select || !tab->select->quick))
7903
my_message(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE,
7904
ER(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE), MYF(0));
7916
void JOIN_TAB::cleanup()
1227
7922
if (cache.buff)
1229
size_t size= cache.end - cache.buff;
1230
global_join_buffer.sub(size);
1231
7923
free(cache.buff);
2515
9627
if (!(left_const && right_const) &&
2516
9628
args[0]->result_type() == args[1]->result_type())
2520
resolve_const_item(session, &args[1], args[0]);
2521
func->update_used_tables();
2522
change_cond_ref_to_const(session, save_list, and_father, and_father,
2525
else if (left_const)
2527
resolve_const_item(session, &args[0], args[1]);
2528
func->update_used_tables();
2529
change_cond_ref_to_const(session, save_list, and_father, and_father,
9632
resolve_const_item(session, &args[1], args[0]);
9633
func->update_used_tables();
9634
change_cond_ref_to_const(session, save_list, and_father, and_father,
9637
else if (left_const)
9639
resolve_const_item(session, &args[0], args[1]);
9640
func->update_used_tables();
9641
change_cond_ref_to_const(session, save_list, and_father, and_father,
9651
Simplify joins replacing outer joins by inner joins whenever it's
9654
The function, during a retrieval of join_list, eliminates those
9655
outer joins that can be converted into inner join, possibly nested.
9656
It also moves the on expressions for the converted outer joins
9657
and from inner joins to conds.
9658
The function also calculates some attributes for nested joins:
9662
- on_expr_dep_tables
9663
The first two attributes are used to test whether an outer join can
9664
be substituted for an inner join. The third attribute represents the
9665
relation 'to be dependent on' for tables. If table t2 is dependent
9666
on table t1, then in any evaluated execution plan table access to
9667
table t2 must precede access to table t2. This relation is used also
9668
to check whether the query contains invalid cross-references.
9669
The forth attribute is an auxiliary one and is used to calculate
9671
As the attribute dep_tables qualifies possibles orders of tables in the
9672
execution plan, the dependencies required by the straight join
9673
modifiers are reflected in this attribute as well.
9674
The function also removes all braces that can be removed from the join
9675
expression without changing its meaning.
9678
An outer join can be replaced by an inner join if the where condition
9679
or the on expression for an embedding nested join contains a conjunctive
9680
predicate rejecting null values for some attribute of the inner tables.
9684
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9686
the predicate t2.b < 5 rejects nulls.
9687
The query is converted first to:
9689
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9691
then to the equivalent form:
9693
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
9697
Similarly the following query:
9699
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
9704
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
9708
One conversion might trigger another:
9710
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
9711
LEFT JOIN t3 ON t3.b=t2.b
9712
WHERE t3 IS NOT NULL =>
9713
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
9714
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
9715
SELECT * FROM t1, t2, t3
9716
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
9719
The function removes all unnecessary braces from the expression
9720
produced by the conversions.
9723
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9725
finally is converted to:
9727
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9732
It also will remove braces from the following queries:
9734
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
9735
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
9738
The benefit of this simplification procedure is that it might return
9739
a query for which the optimizer can evaluate execution plan with more
9740
join orders. With a left join operation the optimizer does not
9741
consider any plan where one of the inner tables is before some of outer
9745
The function is implemented by a recursive procedure. On the recursive
9746
ascent all attributes are calculated, all outer joins that can be
9747
converted are replaced and then all unnecessary braces are removed.
9748
As join list contains join tables in the reverse order sequential
9749
elimination of outer joins does not require extra recursive calls.
9752
Remove all semi-joins that have are within another semi-join (i.e. have
9753
an "ancestor" semi-join nest)
9756
Here is an example of a join query with invalid cross references:
9758
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
9761
@param join reference to the query info
9762
@param join_list list representation of the join to be converted
9763
@param conds conditions to add on expressions for converted joins
9764
@param top true <=> conds is the where condition
9767
- The new condition, if success
9772
simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top,
9776
nested_join_st *nested_join;
9777
TableList *prev_table= 0;
9778
List_iterator<TableList> li(*join_list);
9781
Try to simplify join operations from join_list.
9782
The most outer join operation is checked for conversion first.
9784
while ((table= li++))
9786
table_map used_tables;
9787
table_map not_null_tables= (table_map) 0;
9789
if ((nested_join= table->nested_join))
9792
If the element of join_list is a nested join apply
9793
the procedure to its nested join list first.
9797
Item *expr= table->on_expr;
9799
If an on expression E is attached to the table,
9800
check all null rejected predicates in this expression.
9801
If such a predicate over an attribute belonging to
9802
an inner table of an embedded outer join is found,
9803
the outer join is converted to an inner join and
9804
the corresponding on expression is added to E.
9806
expr= simplify_joins(join, &nested_join->join_list,
9807
expr, false, in_sj || table->sj_on_expr);
9809
if (!table->prep_on_expr || expr != table->on_expr)
9813
table->on_expr= expr;
9814
table->prep_on_expr= expr->copy_andor_structure(join->session);
9817
nested_join->used_tables= (table_map) 0;
9818
nested_join->not_null_tables=(table_map) 0;
9819
conds= simplify_joins(join, &nested_join->join_list, conds, top,
9820
in_sj || table->sj_on_expr);
9821
used_tables= nested_join->used_tables;
9822
not_null_tables= nested_join->not_null_tables;
9826
if (!table->prep_on_expr)
9827
table->prep_on_expr= table->on_expr;
9828
used_tables= table->table->map;
9830
not_null_tables= conds->not_null_tables();
9833
if (table->embedding)
9835
table->embedding->nested_join->used_tables|= used_tables;
9836
table->embedding->nested_join->not_null_tables|= not_null_tables;
9839
if (!table->outer_join || (used_tables & not_null_tables))
9842
For some of the inner tables there are conjunctive predicates
9843
that reject nulls => the outer join can be replaced by an inner join.
9845
table->outer_join= 0;
9848
/* Add ON expression to the WHERE or upper-level ON condition. */
9851
conds= and_conds(conds, table->on_expr);
9852
conds->top_level_item();
9853
/* conds is always a new item as both cond and on_expr existed */
9854
assert(!conds->fixed);
9855
conds->fix_fields(join->session, &conds);
9858
conds= table->on_expr;
9859
table->prep_on_expr= table->on_expr= 0;
9867
Only inner tables of non-convertible outer joins
9868
remain with on_expr.
9872
table->dep_tables|= table->on_expr->used_tables();
9873
if (table->embedding)
9875
table->dep_tables&= ~table->embedding->nested_join->used_tables;
9877
Embedding table depends on tables used
9878
in embedded on expressions.
9880
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
9883
table->dep_tables&= ~table->table->map;
9888
/* The order of tables is reverse: prev_table follows table */
9889
if (prev_table->straight)
9890
prev_table->dep_tables|= used_tables;
9891
if (prev_table->on_expr)
9893
prev_table->dep_tables|= table->on_expr_dep_tables;
9894
table_map prev_used_tables= prev_table->nested_join ?
9895
prev_table->nested_join->used_tables :
9896
prev_table->table->map;
9898
If on expression contains only references to inner tables
9899
we still make the inner tables dependent on the outer tables.
9900
It would be enough to set dependency only on one outer table
9901
for them. Yet this is really a rare case.
9903
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
9904
prev_table->dep_tables|= used_tables;
9911
Flatten nested joins that can be flattened.
9912
no ON expression and not a semi-join => can be flattened.
9915
while ((table= li++))
9917
nested_join= table->nested_join;
9918
if (table->sj_on_expr && !in_sj)
9921
If this is a semi-join that is not contained within another semi-join,
9922
leave it intact (otherwise it is flattened)
9924
join->select_lex->sj_nests.push_back(table);
9926
else if (nested_join && !table->on_expr)
9929
List_iterator<TableList> it(nested_join->join_list);
9932
tbl->embedding= table->embedding;
9933
tbl->join_list= table->join_list;
9935
li.replace(nested_join->join_list);
9943
Assign each nested join structure a bit in nested_join_map.
9945
Assign each nested join structure (except "confluent" ones - those that
9946
embed only one element) a bit in nested_join_map.
9948
@param join Join being processed
9949
@param join_list List of tables
9950
@param first_unused Number of first unused bit in nested_join_map before the
9954
This function is called after simplify_joins(), when there are no
9955
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
9956
we will not run out of bits in nested_join_map.
9959
First unused bit in nested_join_map after the call.
9962
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
9963
uint32_t first_unused)
9965
List_iterator<TableList> li(*join_list);
9967
while ((table= li++))
9969
nested_join_st *nested_join;
9970
if ((nested_join= table->nested_join))
9973
It is guaranteed by simplify_joins() function that a nested join
9974
that has only one child is either
9975
- a single-table view (the child is the underlying table), or
9976
- a single-table semi-join nest
9978
We don't assign bits to such sj-nests because
9979
1. it is redundant (a "sequence" of one table cannot be interleaved
9981
2. we could run out bits in nested_join_map otherwise.
9983
if (nested_join->join_list.elements != 1)
9985
/* Don't assign bits to sj-nests */
9987
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
9988
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
9993
return(first_unused);
9998
Set nested_join_st::counter=0 in all nested joins in passed list.
10000
Recursively set nested_join_st::counter=0 for all nested joins contained in
10001
the passed join_list.
10003
@param join_list List of nested joins to process. It may also contain base
10004
tables which will be ignored.
10007
static void reset_nj_counters(List<TableList> *join_list)
10009
List_iterator<TableList> li(*join_list);
10011
while ((table= li++))
10013
nested_join_st *nested_join;
10014
if ((nested_join= table->nested_join))
10016
nested_join->counter_= 0;
10017
reset_nj_counters(&nested_join->join_list);
2538
10025
Check interleaving with an inner tables of an outer join for
3362
int safe_index_read(JoinTable *tab)
10939
SemiJoinDuplicateElimination: Weed out duplicate row combinations
10942
do_sj_dups_weedout()
10946
1 The row combination is a duplicate (discard it)
10947
0 The row combination is not a duplicate (continue)
10950
int do_sj_dups_weedout(Session *session, SJ_TMP_TABLE *sjtbl)
10953
SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
10954
SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
10955
unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;
10956
unsigned char *nulls_ptr= ptr;
10958
/* Put the the rowids tuple into table->record[0]: */
10960
// 1. Store the length
10961
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
10963
*ptr= (unsigned char)(sjtbl->rowid_len + sjtbl->null_bytes);
10968
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
10972
// 2. Zero the null bytes
10973
if (sjtbl->null_bytes)
10975
memset(ptr, 0, sjtbl->null_bytes);
10976
ptr += sjtbl->null_bytes;
10979
// 3. Put the rowids
10980
for (uint32_t i=0; tab != tab_end; tab++, i++)
10982
handler *h= tab->join_tab->table->file;
10983
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
10985
/* It's a NULL-complemented row */
10986
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
10987
memset(ptr + tab->rowid_offset, 0, h->ref_length);
10991
/* Copy the rowid value */
10992
if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
10993
h->position(tab->join_tab->table->record[0]);
10994
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
10998
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
11001
/* create_myisam_from_heap will generate error if needed */
11002
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
11003
create_myisam_from_heap(session, sjtbl->tmp_table, sjtbl->start_recinfo,
11004
&sjtbl->recinfo, error, 1))
11006
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
11014
SemiJoinDuplicateElimination: Reset the temporary table
11017
int do_sj_reset(SJ_TMP_TABLE *sj_tbl)
11019
if (sj_tbl->tmp_table)
11020
return sj_tbl->tmp_table->file->ha_delete_all_rows();
11025
Process one record of the nested loop join.
11027
This function will evaluate parts of WHERE/ON clauses that are
11028
applicable to the partial record on hand and in case of success
11029
submit this record to the next level of the nested loop.
11032
static enum_nested_loop_state
11033
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
11036
bool not_used_in_distinct=join_tab->not_used_in_distinct;
11037
ha_rows found_records=join->found_records;
11038
COND *select_cond= join_tab->select_cond;
11040
if (error > 0 || (join->session->is_error())) // Fatal error
11041
return NESTED_LOOP_ERROR;
11043
return NESTED_LOOP_NO_MORE_ROWS;
11044
if (join->session->killed) // Aborted by user
11046
join->session->send_kill_message();
11047
return NESTED_LOOP_KILLED; /* purecov: inspected */
11049
if (!select_cond || select_cond->val_int())
11052
There is no select condition or the attached pushed down
11053
condition is true => a match is found.
11056
while (join_tab->first_unmatched && found)
11059
The while condition is always false if join_tab is not
11060
the last inner join table of an outer join operation.
11062
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11064
Mark that a match for current outer table is found.
11065
This activates push down conditional predicates attached
11066
to the all inner tables of the outer join.
11068
first_unmatched->found= 1;
11069
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11071
if (tab->table->reginfo.not_exists_optimize)
11072
return NESTED_LOOP_NO_MORE_ROWS;
11073
/* Check all predicates that has just been activated. */
11075
Actually all predicates non-guarded by first_unmatched->found
11076
will be re-evaluated again. It could be fixed, but, probably,
11077
it's not worth doing now.
11079
if (tab->select_cond && !tab->select_cond->val_int())
11081
/* The condition attached to table tab is false */
11082
if (tab == join_tab)
11087
Set a return point if rejected predicate is attached
11088
not to the last table of the current nest level.
11090
join->return_tab= tab;
11091
return NESTED_LOOP_OK;
11096
Check whether join_tab is not the last inner table
11097
for another embedding outer join.
11099
if ((first_unmatched= first_unmatched->first_upper) &&
11100
first_unmatched->last_inner != join_tab)
11101
first_unmatched= 0;
11102
join_tab->first_unmatched= first_unmatched;
11105
JOIN_TAB *return_tab= join->return_tab;
11106
join_tab->found_match= true;
11107
if (join_tab->check_weed_out_table)
11109
int res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table);
11111
return NESTED_LOOP_ERROR;
11113
return NESTED_LOOP_OK;
11115
else if (join_tab->do_firstmatch)
11118
We should return to the join_tab->do_firstmatch after we have
11119
enumerated all the suffixes for current prefix row combination
11121
return_tab= join_tab->do_firstmatch;
11125
It was not just a return to lower loop level when one
11126
of the newly activated predicates is evaluated as false
11127
(See above join->return_tab= tab).
11129
join->examined_rows++;
11130
join->session->row_count++;
11134
enum enum_nested_loop_state rc;
11135
/* A match from join_tab is found for the current partial join. */
11136
rc= (*join_tab->next_select)(join, join_tab+1, 0);
11137
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11139
if (return_tab < join->return_tab)
11140
join->return_tab= return_tab;
11142
if (join->return_tab < join_tab)
11143
return NESTED_LOOP_OK;
11145
Test if this was a SELECT DISTINCT query on a table that
11146
was not in the field list; In this case we can abort if
11147
we found a row, as no new rows can be added to the result.
11149
if (not_used_in_distinct && found_records != join->found_records)
11150
return NESTED_LOOP_NO_MORE_ROWS;
11153
join_tab->read_record.file->unlock_row();
11158
The condition pushed down to the table join_tab rejects all rows
11159
with the beginning coinciding with the current partial join.
11161
join->examined_rows++;
11162
join->session->row_count++;
11163
join_tab->read_record.file->unlock_row();
11165
return NESTED_LOOP_OK;
11172
Construct a NULL complimented partial join record and feed it to the next
11173
level of the nested loop. This function is used in case we have
11174
an OUTER join and no matching record was found.
11177
static enum_nested_loop_state
11178
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab)
11181
The table join_tab is the first inner table of a outer join operation
11182
and no matches has been found for the current outer row.
11184
JOIN_TAB *last_inner_tab= join_tab->last_inner;
11185
/* Cache variables for faster loop */
11187
for ( ; join_tab <= last_inner_tab ; join_tab++)
11189
/* Change the the values of guard predicate variables. */
11190
join_tab->found= 1;
11191
join_tab->not_null_compl= 0;
11192
/* The outer row is complemented by nulls for each inner tables */
11193
restore_record(join_tab->table,s->default_values); // Make empty record
11194
mark_as_null_row(join_tab->table); // For group by without error
11195
select_cond= join_tab->select_cond;
11196
/* Check all attached conditions for inner table rows. */
11197
if (select_cond && !select_cond->val_int())
11198
return NESTED_LOOP_OK;
11202
The row complemented by nulls might be the first row
11203
of embedding outer joins.
11204
If so, perform the same actions as in the code
11205
for the first regular outer join row above.
11209
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11210
if ((first_unmatched= first_unmatched->first_upper) &&
11211
first_unmatched->last_inner != join_tab)
11212
first_unmatched= 0;
11213
join_tab->first_unmatched= first_unmatched;
11214
if (!first_unmatched)
11216
first_unmatched->found= 1;
11217
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11219
if (tab->select_cond && !tab->select_cond->val_int())
11221
join->return_tab= tab;
11222
return NESTED_LOOP_OK;
11227
The row complemented by nulls satisfies all conditions
11228
attached to inner tables.
11229
Send the row complemented by nulls to be joined with the
11232
return (*join_tab->next_select)(join, join_tab+1, 0);
11236
static enum_nested_loop_state
11237
flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skip_last)
11239
enum_nested_loop_state rc= NESTED_LOOP_OK;
11243
join_tab->table->null_row= 0;
11244
if (!join_tab->cache.records)
11245
return NESTED_LOOP_OK; /* Nothing to do */
11247
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
11248
if (join_tab->use_quick == 2)
11250
if (join_tab->select->quick)
11251
{ /* Used quick select last. reset it */
11252
delete join_tab->select->quick;
11253
join_tab->select->quick=0;
11256
/* read through all records */
11257
if ((error=join_init_read_record(join_tab)))
11259
reset_cache_write(&join_tab->cache);
11260
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
11263
for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
11265
tmp->status=tmp->table->status;
11266
tmp->table->status=0;
11269
info= &join_tab->read_record;
11272
if (join->session->killed)
11274
join->session->send_kill_message();
11275
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
11277
SQL_SELECT *select=join_tab->select;
11278
if (rc == NESTED_LOOP_OK &&
11279
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
11282
reset_cache_read(&join_tab->cache);
11283
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
11285
read_cached_record(join_tab);
11286
if (!select || !select->skip_record())
11289
if (!join_tab->check_weed_out_table ||
11290
!(res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table)))
11292
rc= (join_tab->next_select)(join,join_tab+1,0);
11293
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11295
reset_cache_write(&join_tab->cache);
11300
return NESTED_LOOP_ERROR;
11304
} while (!(error=info->read_record(info)));
11307
read_cached_record(join_tab); // Restore current record
11308
reset_cache_write(&join_tab->cache);
11309
if (error > 0) // Fatal error
11310
return NESTED_LOOP_ERROR; /* purecov: inspected */
11311
for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
11312
tmp2->table->status=tmp2->status;
11313
return NESTED_LOOP_OK;
11316
int safe_index_read(JOIN_TAB *tab)
3365
11319
Table *table= tab->table;
3366
if ((error=table->cursor->index_read_map(table->getInsertRecord(),
11320
if ((error=table->file->index_read_map(table->record[0],
3367
11321
tab->ref.key_buff,
3368
11322
make_prev_keypart_map(tab->ref.key_parts),
3369
11323
HA_READ_KEY_EXACT)))
15374
/** Allocate memory needed for other rollup functions. */
15376
bool JOIN::rollup_init()
15381
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
15382
rollup.state= ROLLUP::STATE_INITED;
15385
Create pointers to the different sum function groups
15386
These are updated by rollup_make_fields()
15388
tmp_table_param.group_parts= send_group_parts;
15390
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
15392
sizeof(List<Item>) +
15393
ref_pointer_array_size)
15394
* send_group_parts )))
15397
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
15398
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
15399
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
15402
Prepare space for field list for the different levels
15403
These will be filled up in rollup_make_fields()
15405
for (i= 0 ; i < send_group_parts ; i++)
15407
rollup.null_items[i]= new (session->mem_root) Item_null_result();
15408
List<Item> *rollup_fields= &rollup.fields[i];
15409
rollup_fields->empty();
15410
rollup.ref_pointer_arrays[i]= ref_array;
15411
ref_array+= all_fields.elements;
15413
for (i= 0 ; i < send_group_parts; i++)
15415
for (j=0 ; j < fields_list.elements ; j++)
15416
rollup.fields[i].push_back(rollup.null_items[i]);
15418
List_iterator<Item> it(all_fields);
15420
while ((item= it++))
15422
order_st *group_tmp;
15423
bool found_in_group= 0;
15425
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
15427
if (*group_tmp->item == item)
15429
item->maybe_null= 1;
15431
if (item->const_item())
15434
For ROLLUP queries each constant item referenced in GROUP BY list
15435
is wrapped up into an Item_func object yielding the same value
15436
as the constant item. The objects of the wrapper class are never
15437
considered as constant items and besides they inherit all
15438
properties of the Item_result_field class.
15439
This wrapping allows us to ensure writing constant items
15440
into temporary tables whenever the result of the ROLLUP
15441
operation has to be written into a temporary table, e.g. when
15442
ROLLUP is used together with DISTINCT in the SELECT list.
15443
Usually when creating temporary tables for a intermidiate
15444
result we do not include fields for constant expressions.
15446
Item* new_item= new Item_func_rollup_const(item);
15449
new_item->fix_fields(session, (Item **) 0);
15450
session->change_item_tree(it.ref(), new_item);
15451
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
15453
if (*tmp->item == item)
15454
session->change_item_tree(tmp->item, new_item);
15459
if (item->type() == Item::FUNC_ITEM && !found_in_group)
15461
bool changed= false;
15462
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
15465
We have to prevent creation of a field in a temporary table for
15466
an expression that contains GROUP BY attributes.
15467
Marking the expression item as 'with_sum_func' will ensure this.
15470
item->with_sum_func= 1;
15478
Fill up rollup structures with pointers to fields to use.
15480
Creates copies of item_sum items for each sum level.
15482
@param fields_arg List of all fields (hidden and real ones)
15483
@param sel_fields Pointer to selected fields
15484
@param func Store here a pointer to all fields
15488
In this case func is pointing to next not used element.
15493
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields,
15496
List_iterator_fast<Item> it(fields_arg);
15497
Item *first_field= sel_fields.head();
15501
Create field lists for the different levels
15503
The idea here is to have a separate field list for each rollup level to
15504
avoid all runtime checks of which columns should be NULL.
15506
The list is stored in reverse order to get sum function in such an order
15507
in func that it makes it easy to reset them with init_sum_functions()
15509
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15511
rollup.fields[0] will contain list where a,b,c is NULL
15512
rollup.fields[1] will contain list where b,c is NULL
15514
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
15516
sum_funcs_end[0] points to all sum functions
15517
sum_funcs_end[1] points to all sum functions, except grand totals
15521
for (level=0 ; level < send_group_parts ; level++)
15524
uint32_t pos= send_group_parts - level -1;
15525
bool real_fields= 0;
15527
List_iterator<Item> new_it(rollup.fields[pos]);
15528
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
15529
order_st *start_group;
15531
/* Point to first hidden field */
15532
Item **ref_array= ref_array_start + fields_arg.elements-1;
15534
/* Remember where the sum functions ends for the previous level */
15535
sum_funcs_end[pos+1]= *func;
15537
/* Find the start of the group for this level */
15538
for (i= 0, start_group= group_list ;
15540
start_group= start_group->next)
15544
while ((item= it++))
15546
if (item == first_field)
15548
real_fields= 1; // End of hidden fields
15549
ref_array= ref_array_start;
15552
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
15553
(!((Item_sum*) item)->depended_from() ||
15554
((Item_sum *)item)->depended_from() == select_lex))
15558
This is a top level summary function that must be replaced with
15559
a sum function that is reset for this level.
15561
NOTE: This code creates an object which is not that nice in a
15562
sub select. Fortunately it's not common to have rollup in
15565
item= item->copy_or_same(session);
15566
((Item_sum*) item)->make_unique();
15567
*(*func)= (Item_sum*) item;
15572
/* Check if this is something that is part of this group by */
15573
order_st *group_tmp;
15574
for (group_tmp= start_group, i= pos ;
15575
group_tmp ; group_tmp= group_tmp->next, i++)
15577
if (*group_tmp->item == item)
15580
This is an element that is used by the GROUP BY and should be
15581
set to NULL in this level
15583
Item_null_result *null_item= new (session->mem_root) Item_null_result();
15586
item->maybe_null= 1; // Value will be null sometimes
15587
null_item->result_field= item->get_tmp_table_field();
15596
(void) new_it++; // Point to next item
15597
new_it.replace(item); // Replace previous
15604
sum_funcs_end[0]= *func; // Point to last function
15609
Send all rollup levels higher than the current one to the client.
15613
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15616
@param idx Level we are on:
15617
- 0 = Total sum level
15618
- 1 = First group changed (a)
15619
- 2 = Second group changed (a,b)
15624
1 If send_data_failed()
15627
int JOIN::rollup_send_data(uint32_t idx)
15630
for (i= send_group_parts ; i-- > idx ; )
15632
/* Get reference pointers to sum functions in place */
15633
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15634
ref_pointer_array_size);
15635
if ((!having || having->val_int()))
15637
if (send_records < unit->select_limit_cnt && do_send_rows &&
15638
result->send_data(rollup.fields[i]))
15643
/* Restore ref_pointer_array */
15644
set_items_ref_array(current_ref_pointer_array);
15649
Write all rollup levels higher than the current one to a temp table.
15653
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
15656
@param idx Level we are on:
15657
- 0 = Total sum level
15658
- 1 = First group changed (a)
15659
- 2 = Second group changed (a,b)
15660
@param table reference to temp table
15665
1 if write_data_failed()
15668
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
15671
for (i= send_group_parts ; i-- > idx ; )
15673
/* Get reference pointers to sum functions in place */
15674
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15675
ref_pointer_array_size);
15676
if ((!having || having->val_int()))
15680
List_iterator_fast<Item> it(rollup.fields[i]);
15681
while ((item= it++))
15683
if (item->type() == Item::NULL_ITEM && item->is_result_field())
15684
item->save_in_result_field(1);
15686
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
15687
if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
15689
if (create_myisam_from_heap(session, table_arg,
15690
tmp_table_param.start_recinfo,
15691
&tmp_table_param.recinfo,
15697
/* Restore ref_pointer_array */
15698
set_items_ref_array(current_ref_pointer_array);
15703
clear results if there are not rows found for group
15704
(end_send_group/end_write_group)
15709
clear_tables(this);
15710
copy_fields(&tmp_table_param);
15714
Item_sum *func, **func_ptr= sum_funcs;
15715
while ((func= *(func_ptr++)))
15723
Send a description about what how the select will be done to stdout.
15726
void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
15727
bool distinct,const char *message)
15729
List<Item> field_list;
15730
List<Item> item_list;
15731
Session *session=join->session;
15732
select_result *result=join->result;
15733
Item *item_null= new Item_null();
15734
const CHARSET_INFO * const cs= system_charset_info;
15736
/* Don't log this into the slow query log */
15737
session->server_status&= ~(SERVER_QUERY_NO_INDEX_USED | SERVER_QUERY_NO_GOOD_INDEX_USED);
15738
join->unit->offset_limit_cnt= 0;
15741
NOTE: the number/types of items pushed into item_list must be in sync with
15742
EXPLAIN column types as they're "defined" in Session::send_explain_fields()
15746
item_list.push_back(new Item_int((int32_t)
15747
join->select_lex->select_number));
15748
item_list.push_back(new Item_string(join->select_lex->type,
15749
strlen(join->select_lex->type), cs));
15750
for (uint32_t i=0 ; i < 7; i++)
15751
item_list.push_back(item_null);
15752
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15753
item_list.push_back(item_null);
15755
item_list.push_back(new Item_string(message,strlen(message),cs));
15756
if (result->send_data(item_list))
15759
else if (join->select_lex == join->unit->fake_select_lex)
15762
here we assume that the query will return at least two rows, so we
15763
show "filesort" in EXPLAIN. Of course, sometimes we'll be wrong
15764
and no filesort will be actually done, but executing all selects in
15765
the UNION to provide precise EXPLAIN information will hardly be
15768
char table_name_buffer[NAME_LEN];
15771
item_list.push_back(new Item_null);
15773
item_list.push_back(new Item_string(join->select_lex->type,
15774
strlen(join->select_lex->type),
15778
Select_Lex *sl= join->unit->first_select();
15779
uint32_t len= 6, lastop= 0;
15780
memcpy(table_name_buffer, STRING_WITH_LEN("<union"));
15781
for (; sl && len + lastop + 5 < NAME_LEN; sl= sl->next_select())
15784
lastop= snprintf(table_name_buffer + len, NAME_LEN - len,
15785
"%u,", sl->select_number);
15787
if (sl || len + lastop >= NAME_LEN)
15789
memcpy(table_name_buffer + len, STRING_WITH_LEN("...>") + 1);
15795
table_name_buffer[len - 1]= '>'; // change ',' to '>'
15797
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15800
item_list.push_back(new Item_string(join_type_str[JT_ALL],
15801
strlen(join_type_str[JT_ALL]),
15803
/* possible_keys */
15804
item_list.push_back(item_null);
15806
item_list.push_back(item_null);
15808
item_list.push_back(item_null);
15810
item_list.push_back(item_null);
15812
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15813
item_list.push_back(item_null);
15815
item_list.push_back(item_null);
15817
if (join->unit->global_parameters->order_list.first)
15818
item_list.push_back(new Item_string("Using filesort",
15821
item_list.push_back(new Item_string("", 0, cs));
15823
if (result->send_data(item_list))
15828
table_map used_tables=0;
15829
for (uint32_t i=0 ; i < join->tables ; i++)
15831
JOIN_TAB *tab=join->join_tab+i;
15832
Table *table=tab->table;
15833
TableList *table_list= tab->table->pos_in_table_list;
15835
char buff1[512], buff2[512], buff3[512];
15836
char keylen_str_buf[64];
15837
String extra(buff, sizeof(buff),cs);
15838
char table_name_buffer[NAME_LEN];
15839
String tmp1(buff1,sizeof(buff1),cs);
15840
String tmp2(buff2,sizeof(buff2),cs);
15841
String tmp3(buff3,sizeof(buff3),cs);
15850
item_list.push_back(new Item_uint((uint32_t)
15851
join->select_lex->select_number));
15853
item_list.push_back(new Item_string(join->select_lex->type,
15854
strlen(join->select_lex->type),
15856
if (tab->type == JT_ALL && tab->select && tab->select->quick)
15858
quick_type= tab->select->quick->get_type();
15859
if ((quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) ||
15860
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
15861
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION))
15862
tab->type = JT_INDEX_MERGE;
15864
tab->type = JT_RANGE;
15867
if (table->derived_select_number)
15869
/* Derived table name generation */
15870
int len= snprintf(table_name_buffer, sizeof(table_name_buffer)-1,
15872
table->derived_select_number);
15873
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15877
TableList *real_table= table->pos_in_table_list;
15878
item_list.push_back(new Item_string(real_table->alias,
15879
strlen(real_table->alias),
15882
/* "type" column */
15883
item_list.push_back(new Item_string(join_type_str[tab->type],
15884
strlen(join_type_str[tab->type]),
15886
/* Build "possible_keys" value and add it to item_list */
15887
if (!tab->keys.is_clear_all())
15890
for (j=0 ; j < table->s->keys ; j++)
15892
if (tab->keys.is_set(j))
15896
tmp1.append(table->key_info[j].name,
15897
strlen(table->key_info[j].name),
15898
system_charset_info);
15903
item_list.push_back(new Item_string(tmp1.ptr(),tmp1.length(),cs));
15905
item_list.push_back(item_null);
15907
/* Build "key", "key_len", and "ref" values and add them to item_list */
15908
if (tab->ref.key_parts)
15910
KEY *key_info=table->key_info+ tab->ref.key;
15911
register uint32_t length;
15912
item_list.push_back(new Item_string(key_info->name,
15913
strlen(key_info->name),
15914
system_charset_info));
15915
length= int64_t2str(tab->ref.key_length, keylen_str_buf, 10) -
15917
item_list.push_back(new Item_string(keylen_str_buf, length,
15918
system_charset_info));
15919
for (store_key **ref=tab->ref.key_copy ; *ref ; ref++)
15923
tmp2.append((*ref)->name(), strlen((*ref)->name()),
15924
system_charset_info);
15926
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15928
else if (tab->type == JT_NEXT)
15930
KEY *key_info=table->key_info+ tab->index;
15931
register uint32_t length;
15932
item_list.push_back(new Item_string(key_info->name,
15933
strlen(key_info->name),cs));
15934
length= int64_t2str(key_info->key_length, keylen_str_buf, 10) -
15936
item_list.push_back(new Item_string(keylen_str_buf,
15938
system_charset_info));
15939
item_list.push_back(item_null);
15941
else if (tab->select && tab->select->quick)
15943
tab->select->quick->add_keys_and_lengths(&tmp2, &tmp3);
15944
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15945
item_list.push_back(new Item_string(tmp3.ptr(),tmp3.length(),cs));
15946
item_list.push_back(item_null);
15950
if (table_list->schema_table && table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
15952
const char *tmp_buff;
15954
if (table_list->has_db_lookup_value)
15956
f_idx= table_list->schema_table->idx_field1;
15957
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15958
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15960
if (table_list->has_table_lookup_value)
15962
if (table_list->has_db_lookup_value)
15964
f_idx= table_list->schema_table->idx_field2;
15965
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15966
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15969
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15971
item_list.push_back(item_null);
15974
item_list.push_back(item_null);
15975
item_list.push_back(item_null);
15976
item_list.push_back(item_null);
15979
/* Add "rows" field to item_list. */
15980
if (table_list->schema_table)
15983
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15984
item_list.push_back(item_null);
15986
item_list.push_back(item_null);
15990
double examined_rows;
15991
if (tab->select && tab->select->quick)
15992
examined_rows= rows2double(tab->select->quick->records);
15993
else if (tab->type == JT_NEXT || tab->type == JT_ALL)
15994
examined_rows= rows2double(tab->limit ? tab->limit :
15995
tab->table->file->records());
15997
examined_rows= join->best_positions[i].records_read;
15999
item_list.push_back(new Item_int((int64_t) (uint64_t) examined_rows,
16000
MY_INT64_NUM_DECIMAL_DIGITS));
16002
/* Add "filtered" field to item_list. */
16003
if (join->session->lex->describe & DESCRIBE_EXTENDED)
16007
f= (float) (100.0 * join->best_positions[i].records_read /
16009
item_list.push_back(new Item_float(f, 2));
16013
/* Build "Extra" field and add it to item_list. */
16014
bool key_read=table->key_read;
16015
if ((tab->type == JT_NEXT || tab->type == JT_CONST) &&
16016
table->covering_keys.is_set(tab->index))
16018
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT &&
16019
!((QUICK_ROR_INTERSECT_SELECT*)tab->select->quick)->need_to_fetch_row)
16023
item_list.push_back(new Item_string(tab->info,strlen(tab->info),cs));
16024
else if (tab->packed_info & TAB_INFO_HAVE_VALUE)
16026
if (tab->packed_info & TAB_INFO_USING_INDEX)
16027
extra.append(STRING_WITH_LEN("; Using index"));
16028
if (tab->packed_info & TAB_INFO_USING_WHERE)
16029
extra.append(STRING_WITH_LEN("; Using where"));
16030
if (tab->packed_info & TAB_INFO_FULL_SCAN_ON_NULL)
16031
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16032
/* Skip initial "; "*/
16033
const char *str= extra.ptr();
16034
uint32_t len= extra.length();
16040
item_list.push_back(new Item_string(str, len, cs));
16044
uint32_t keyno= MAX_KEY;
16045
if (tab->ref.key_parts)
16046
keyno= tab->ref.key;
16047
else if (tab->select && tab->select->quick)
16048
keyno = tab->select->quick->index;
16050
if (keyno != MAX_KEY && keyno == table->file->pushed_idx_cond_keyno &&
16051
table->file->pushed_idx_cond)
16052
extra.append(STRING_WITH_LEN("; Using index condition"));
16054
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
16055
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
16056
quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE)
16058
extra.append(STRING_WITH_LEN("; Using "));
16059
tab->select->quick->add_info_string(&extra);
16063
if (tab->use_quick == 2)
16065
/* 4 bits per 1 hex digit + terminating '\0' */
16066
char buf[MAX_KEY / 4 + 1];
16067
extra.append(STRING_WITH_LEN("; Range checked for each "
16068
"record (index map: 0x"));
16069
extra.append(tab->keys.print(buf));
16072
else if (tab->select->cond)
16074
const COND *pushed_cond= tab->table->file->pushed_cond;
16076
if (session->variables.engine_condition_pushdown && pushed_cond)
16078
extra.append(STRING_WITH_LEN("; Using where with pushed "
16080
if (session->lex->describe & DESCRIBE_EXTENDED)
16082
extra.append(STRING_WITH_LEN(": "));
16083
((COND *)pushed_cond)->print(&extra, QT_ORDINARY);
16087
extra.append(STRING_WITH_LEN("; Using where"));
16092
if (quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
16093
extra.append(STRING_WITH_LEN("; Using index for group-by"));
16095
extra.append(STRING_WITH_LEN("; Using index"));
16097
if (table->reginfo.not_exists_optimize)
16098
extra.append(STRING_WITH_LEN("; Not exists"));
16100
if (quick_type == QUICK_SELECT_I::QS_TYPE_RANGE &&
16101
!(((QUICK_RANGE_SELECT*)(tab->select->quick))->mrr_flags &
16102
HA_MRR_USE_DEFAULT_IMPL))
16104
extra.append(STRING_WITH_LEN("; Using MRR"));
16107
if (table_list->schema_table &&
16108
table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
16110
if (!table_list->table_open_method)
16111
extra.append(STRING_WITH_LEN("; Skip_open_table"));
16112
else if (table_list->table_open_method == OPEN_FRM_ONLY)
16113
extra.append(STRING_WITH_LEN("; Open_frm_only"));
16115
extra.append(STRING_WITH_LEN("; Open_full_table"));
16116
if (table_list->has_db_lookup_value &&
16117
table_list->has_table_lookup_value)
16118
extra.append(STRING_WITH_LEN("; Scanned 0 databases"));
16119
else if (table_list->has_db_lookup_value ||
16120
table_list->has_table_lookup_value)
16121
extra.append(STRING_WITH_LEN("; Scanned 1 database"));
16123
extra.append(STRING_WITH_LEN("; Scanned all databases"));
16125
if (need_tmp_table)
16128
extra.append(STRING_WITH_LEN("; Using temporary"));
16133
extra.append(STRING_WITH_LEN("; Using filesort"));
16135
if (distinct & test_all_bits(used_tables,session->used_tables))
16136
extra.append(STRING_WITH_LEN("; Distinct"));
16138
if (tab->insideout_match_tab)
16140
extra.append(STRING_WITH_LEN("; LooseScan"));
16143
if (tab->flush_weedout_table)
16144
extra.append(STRING_WITH_LEN("; Start temporary"));
16145
else if (tab->check_weed_out_table)
16146
extra.append(STRING_WITH_LEN("; End temporary"));
16147
else if (tab->do_firstmatch)
16149
extra.append(STRING_WITH_LEN("; FirstMatch("));
16150
Table *prev_table=tab->do_firstmatch->table;
16151
if (prev_table->derived_select_number)
16153
char namebuf[NAME_LEN];
16154
/* Derived table name generation */
16155
int len= snprintf(namebuf, sizeof(namebuf)-1,
16157
prev_table->derived_select_number);
16158
extra.append(namebuf, len);
16161
extra.append(prev_table->pos_in_table_list->alias);
16162
extra.append(STRING_WITH_LEN(")"));
16165
for (uint32_t part= 0; part < tab->ref.key_parts; part++)
16167
if (tab->ref.cond_guards[part])
16169
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16174
if (i > 0 && tab[-1].next_select == sub_select_cache)
16175
extra.append(STRING_WITH_LEN("; Using join buffer"));
16177
/* Skip initial "; "*/
16178
const char *str= extra.ptr();
16179
uint32_t len= extra.length();
16185
item_list.push_back(new Item_string(str, len, cs));
16187
// For next iteration
16188
used_tables|=table->map;
16189
if (result->send_data(item_list))
16193
for (Select_Lex_Unit *unit= join->select_lex->first_inner_unit();
16195
unit= unit->next_unit())
16197
if (mysql_explain_union(session, unit, result))
16204
bool mysql_explain_union(Session *session, Select_Lex_Unit *unit, select_result *result)
16207
Select_Lex *first= unit->first_select();
16209
for (Select_Lex *sl= first;
16211
sl= sl->next_select())
16213
// drop UNCACHEABLE_EXPLAIN, because it is for internal usage only
16214
uint8_t uncacheable= (sl->uncacheable & ~UNCACHEABLE_EXPLAIN);
16215
sl->type= (((&session->lex->select_lex)==sl)?
16216
(sl->first_inner_unit() || sl->next_select() ?
16217
"PRIMARY" : "SIMPLE"):
16219
((sl->linkage == DERIVED_TABLE_TYPE) ?
16221
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16222
"DEPENDENT SUBQUERY":
16223
(uncacheable?"UNCACHEABLE SUBQUERY":
16225
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16227
uncacheable?"UNCACHEABLE UNION":
16229
sl->options|= SELECT_DESCRIBE;
16231
if (unit->is_union())
16233
unit->fake_select_lex->select_number= UINT_MAX; // jost for initialization
16234
unit->fake_select_lex->type= "UNION RESULT";
16235
unit->fake_select_lex->options|= SELECT_DESCRIBE;
16236
if (!(res= unit->prepare(session, result, SELECT_NO_UNLOCK | SELECT_DESCRIBE)))
16238
res|= unit->cleanup();
16242
session->lex->current_select= first;
16243
unit->set_limit(unit->global_parameters);
16244
res= mysql_select(session, &first->ref_pointer_array,
16245
(TableList*) first->table_list.first,
16246
first->with_wild, first->item_list,
16248
first->order_list.elements +
16249
first->group_list.elements,
16250
(order_st*) first->order_list.first,
16251
(order_st*) first->group_list.first,
16253
(order_st*) session->lex->proc_list.first,
16254
first->options | session->options | SELECT_DESCRIBE,
16255
result, unit, first);
16257
return(res || session->is_error());
6257
16261
static void print_table_array(Session *session, String *str, TableList **table,
6258
16262
TableList **end)