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>
53
#if defined(CMATH_NAMESPACE)
54
using namespace CMATH_NAMESPACE;
72
57
using namespace std;
77
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);
59
const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
60
"MAYBE_REF","ALL","range","index",
61
"ref_or_null","unique_subquery","index_subquery",
65
struct st_sargable_param;
67
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
68
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds,
69
DYNAMIC_ARRAY *keyuse);
70
static bool update_ref_and_keys(Session *session, DYNAMIC_ARRAY *keyuse,
72
uint32_t tables, COND *conds,
73
COND_EQUAL *cond_equal,
74
table_map table_map, Select_Lex *select_lex,
75
st_sargable_param **sargables);
76
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
77
static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);
78
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
79
table_map used_tables);
80
static bool choose_plan(JOIN *join,table_map join_tables);
82
static void best_access_path(JOIN *join, JOIN_TAB *s, Session *session,
83
table_map remaining_tables, uint32_t idx,
84
double record_count, double read_time);
85
static void optimize_straight_join(JOIN *join, table_map join_tables);
86
static bool greedy_search(JOIN *join, table_map remaining_tables,
87
uint32_t depth, uint32_t prune_level);
88
static bool best_extension_by_limited_search(JOIN *join,
89
table_map remaining_tables,
90
uint32_t idx, double record_count,
91
double read_time, uint32_t depth,
92
uint32_t prune_level);
93
static uint32_t determine_search_depth(JOIN* join);
94
extern "C" int join_tab_cmp(const void* ptr1, const void* ptr2);
95
extern "C" int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
97
TODO: 'find_best' is here only temporarily until 'greedy_search' is
100
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index,
101
double record_count,double read_time);
102
static uint32_t cache_record_length(JOIN *join,uint32_t index);
103
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
104
static bool get_best_combination(JOIN *join);
105
static store_key *get_store_key(Session *session,
106
KEYUSE *keyuse, table_map used_tables,
107
KEY_PART_INFO *key_part, unsigned char *key_buff,
108
uint32_t maybe_null);
109
static bool make_simple_join(JOIN *join,Table *tmp_table);
110
static void make_outerjoin_info(JOIN *join);
111
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
112
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
113
static bool only_eq_ref_tables(JOIN *join, order_st *order, table_map tables);
114
static void update_depend_map(JOIN *join);
115
static void update_depend_map(JOIN *join, order_st *order);
116
static order_st *remove_const(JOIN *join,order_st *first_order,COND *cond,
117
bool change_list, bool *simple_order);
118
static int return_zero_rows(JOIN *join, select_result *res,TableList *tables,
119
List<Item> &fields, bool send_row,
120
uint64_t select_options, const char *info,
78
122
static COND *build_equal_items(Session *session, COND *cond,
79
123
COND_EQUAL *inherited,
80
124
List<TableList> *join_list,
81
125
COND_EQUAL **cond_equal_ref);
126
static COND* substitute_for_best_equal_field(COND *cond,
127
COND_EQUAL *cond_equal,
128
void *table_join_idx);
129
static COND *simplify_joins(JOIN *join, List<TableList> *join_list,
130
COND *conds, bool top, bool in_sj);
131
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
132
static void restore_prev_nj_state(JOIN_TAB *last);
133
static void reset_nj_counters(List<TableList> *join_list);
134
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
135
uint32_t first_unused);
138
void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);
139
static void restore_prev_sj_state(const table_map remaining_tables,
140
const JOIN_TAB *tab);
142
static COND *optimize_cond(JOIN *join, COND *conds,
143
List<TableList> *join_list,
144
Item::cond_result *cond_value);
145
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
146
static int do_select(JOIN *join,List<Item> *fields,Table *tmp_table);
148
static enum_nested_loop_state
149
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
151
static enum_nested_loop_state
152
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
153
static enum_nested_loop_state
154
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
155
static enum_nested_loop_state
156
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
157
static enum_nested_loop_state
158
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
159
static enum_nested_loop_state
160
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
161
static enum_nested_loop_state
162
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
164
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
165
static int join_read_system(JOIN_TAB *tab);
166
static int join_read_const(JOIN_TAB *tab);
167
static int join_read_key(JOIN_TAB *tab);
168
static int join_read_always_key(JOIN_TAB *tab);
169
static int join_read_last_key(JOIN_TAB *tab);
170
static int join_no_more_records(READ_RECORD *info);
171
static int join_read_next(READ_RECORD *info);
172
static int join_read_next_different(READ_RECORD *info);
173
static int join_init_quick_read_record(JOIN_TAB *tab);
174
static int test_if_quick_select(JOIN_TAB *tab);
175
static int join_init_read_record(JOIN_TAB *tab);
176
static int join_read_first(JOIN_TAB *tab);
177
static int join_read_next_same(READ_RECORD *info);
178
static int join_read_next_same_diff(READ_RECORD *info);
179
static int join_read_last(JOIN_TAB *tab);
180
static int join_read_prev_same(READ_RECORD *info);
181
static int join_read_prev(READ_RECORD *info);
182
int join_read_always_key_or_null(JOIN_TAB *tab);
183
int join_read_next_same_or_null(READ_RECORD *info);
184
static COND *make_cond_for_table(COND *cond,table_map table,
185
table_map used_table,
186
bool exclude_expensive_cond);
83
187
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);
188
static bool test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,
189
ha_rows select_limit, bool no_changes,
191
static bool list_contains_unique_index(Table *table,
192
bool (*find_func) (Field *, void *), void *data);
193
static bool find_field_in_item_list (Field *field, void *data);
194
static bool find_field_in_order_list (Field *field, void *data);
195
static int create_sort_index(Session *session, JOIN *join, order_st *order,
196
ha_rows filesort_limit, ha_rows select_limit,
198
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields,
200
static int remove_dup_with_compare(Session *session, Table *entry, Field **field,
201
uint32_t offset, Item *having);
202
static int remove_dup_with_hash_index(Session *session,Table *table,
203
uint32_t field_count, Field **first_field,
204
uint32_t key_length, Item *having);
205
static int join_init_cache(Session *session,JOIN_TAB *tables,uint32_t table_count);
206
static uint32_t used_blob_length(CACHE_FIELD **ptr);
207
static bool store_record_in_cache(JOIN_CACHE *cache);
208
static void reset_cache_read(JOIN_CACHE *cache);
209
static void reset_cache_write(JOIN_CACHE *cache);
210
static void read_cached_record(JOIN_TAB *tab);
211
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
212
static order_st *create_distinct_group(Session *session, Item **ref_pointer_array,
213
order_st *order, List<Item> &fields,
214
List<Item> &all_fields,
215
bool *all_order_by_fields_used);
216
static bool test_if_subpart(order_st *a,order_st *b);
217
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
218
static void calc_group_buffer(JOIN *join,order_st *group);
219
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
220
static bool alloc_group_fields(JOIN *join,order_st *group);
221
// Create list for using with tempory table
222
static bool change_to_use_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
// Create list for using with tempory table
227
static bool change_refs_to_tmp_fields(Session *session, Item **ref_pointer_array,
228
List<Item> &new_list1,
229
List<Item> &new_list2,
230
uint32_t elements, List<Item> &items);
231
static void init_tmptable_sum_functions(Item_sum **func);
232
static void update_tmptable_sum_func(Item_sum **func,Table *tmp_table);
233
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
234
static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab);
235
static bool setup_sum_funcs(Session *session, Item_sum **func_ptr);
236
static bool init_sum_functions(Item_sum **func, Item_sum **end);
237
static bool update_sum_func(Item_sum **func);
238
void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
239
bool distinct, const char *message=NULL);
240
static Item *remove_additional_cond(Item* conds);
241
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
242
static bool test_if_ref(Item_field *left_item,Item *right_item);
243
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
244
Item *new_cond, bool fix_fields);
93
246
static bool eval_const_cond(COND *cond)
95
248
return ((Item_func*) cond)->val_int() ? true : false;
99
253
This is used to mark equalities that were made from i-th IN-equality.
100
254
We limit semi-join InsideOut optimization to handling max 64 inequalities,
423
Function to setup clauses without sum functions.
425
inline int setup_without_group(Session *session, Item **ref_pointer_array,
429
List<Item> &all_fields,
432
order_st *group, bool *hidden_group_fields)
435
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
437
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
438
res= setup_conds(session, tables, leaves, conds);
440
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
441
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
443
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
444
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
445
group, hidden_group_fields);
446
session->lex->allow_sum_func= save_allow_sum_func;
276
450
/*****************************************************************************
277
451
Check fields, find best join, do the select and output fields.
278
select_query assumes that all tables are already opened
452
mysql_select assumes that all tables are already opened
279
453
*****************************************************************************/
456
Prepare of whole select (including sub queries in future).
459
Add check of calculation of GROUP functions and fields:
460
SELECT COUNT(*)+table.col1 from table1;
468
JOIN::prepare(Item ***rref_pointer_array,
469
TableList *tables_init,
470
uint32_t wild_num, COND *conds_init, uint32_t og_num,
471
order_st *order_init, order_st *group_init,
473
order_st *proc_param_init, Select_Lex *select_lex_arg,
474
Select_Lex_Unit *unit_arg)
476
// to prevent double initialization on EXPLAIN
482
group_list= group_init;
484
proc_param= proc_param_init;
485
tables_list= tables_init;
486
select_lex= select_lex_arg;
487
select_lex->join= this;
488
join_list= &select_lex->top_join_list;
489
union_part= unit_arg->is_union();
491
session->lex->current_select->is_item_list_lookup= 1;
493
If we have already executed SELECT, then it have not sense to prevent
494
its table from update (see unique_table())
496
if (session->derived_tables_processing)
497
select_lex->exclude_from_table_unique_test= true;
499
/* Check that all tables, fields, conds and order are ok */
501
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
502
setup_tables_and_check_access(session, &select_lex->context, join_list,
503
tables_list, &select_lex->leaf_tables,
507
TableList *table_ptr;
508
for (table_ptr= select_lex->leaf_tables;
510
table_ptr= table_ptr->next_leaf)
513
if (setup_wild(session, tables_list, fields_list, &all_fields, wild_num) ||
514
select_lex->setup_ref_array(session, og_num) ||
515
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
517
setup_without_group(session, (*rref_pointer_array), tables_list,
518
select_lex->leaf_tables, fields_list,
519
all_fields, &conds, order, group_list,
520
&hidden_group_fields))
521
return(-1); /* purecov: inspected */
523
ref_pointer_array= *rref_pointer_array;
527
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
528
session->where="having clause";
529
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
530
select_lex->having_fix_field= 1;
531
bool having_fix_rc= (!having->fixed &&
532
(having->fix_fields(session, &having) ||
533
having->check_cols(1)));
534
select_lex->having_fix_field= 0;
535
if (having_fix_rc || session->is_error())
536
return(-1); /* purecov: inspected */
537
session->lex->allow_sum_func= save_allow_sum_func;
541
Item_subselect *subselect;
542
Item_in_subselect *in_subs= NULL;
544
Are we in a subquery predicate?
545
TODO: the block below will be executed for every PS execution without need.
547
if ((subselect= select_lex->master_unit()->item))
549
bool do_semijoin= !test(session->variables.optimizer_switch &
550
OPTIMIZER_SWITCH_NO_SEMIJOIN);
551
if (subselect->substype() == Item_subselect::IN_SUBS)
552
in_subs= (Item_in_subselect*)subselect;
555
Check if we're in subquery that is a candidate for flattening into a
556
semi-join (which is done done in flatten_subqueries()). The
558
1. Subquery predicate is an IN/=ANY subq predicate
559
2. Subquery is a single SELECT (not a UNION)
560
3. Subquery does not have GROUP BY or order_st BY
561
4. Subquery does not use aggregate functions or HAVING
562
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
563
6. No execution method was already chosen (by a prepared statement).
565
(*). We are not in a subquery of a single table UPDATE/DELETE that
566
doesn't have a JOIN (TODO: We should handle this at some
567
point by switching to multi-table UPDATE/DELETE)
569
(**). We're not in a confluent table-less subquery, like
573
!select_lex->master_unit()->first_select()->next_select() && // 2
574
!select_lex->group_list.elements && !order && // 3
575
!having && !select_lex->with_sum_func && // 4
576
session->session_marker && // 5
577
select_lex->outer_select()->join && // (*)
578
select_lex->master_unit()->first_select()->leaf_tables && // (**)
580
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
583
if (!in_subs->left_expr->fixed &&
584
in_subs->left_expr->fix_fields(session, &in_subs->left_expr))
589
Check that the right part of the subselect contains no more than one
590
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
592
if (subselect->substype() == Item_subselect::IN_SUBS &&
593
(select_lex->item_list.elements !=
594
((Item_in_subselect*)subselect)->left_expr->cols()))
596
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
601
/* Register the subquery for further processing */
602
select_lex->outer_select()->join->sj_subselects.append(session->mem_root, in_subs);
603
in_subs->expr_join_nest= (TableList*)session->session_marker;
607
bool do_materialize= !test(session->variables.optimizer_switch &
608
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
610
Check if the subquery predicate can be executed via materialization.
611
The required conditions are:
612
1. Subquery predicate is an IN/=ANY subq predicate
613
2. Subquery is a single SELECT (not a UNION)
614
3. Subquery is not a table-less query. In this case there is no
615
point in materializing.
616
4. Subquery predicate is a top-level predicate
617
(this implies it is not negated)
618
TODO: this is a limitation that should be lifeted once we
619
implement correct NULL semantics (WL#3830)
620
5. Subquery is non-correlated
622
This is an overly restrictive condition. It can be extended to:
623
(Subquery is non-correlated ||
624
Subquery is correlated to any query outer to IN predicate ||
625
(Subquery is correlated to the immediate outer query &&
626
Subquery !contains {GROUP BY, order_st BY [LIMIT],
627
aggregate functions) && subquery predicate is not under "NOT IN"))
628
6. No execution method was already chosen (by a prepared statement).
630
(*) The subquery must be part of a SELECT statement. The current
631
condition also excludes multi-table update statements.
633
We have to determine whether we will perform subquery materialization
634
before calling the IN=>EXISTS transformation, so that we know whether to
635
perform the whole transformation or only that part of it which wraps
636
Item_in_subselect in an Item_in_optimizer.
638
if (do_materialize &&
640
!select_lex->master_unit()->first_select()->next_select() && // 2
641
select_lex->master_unit()->first_select()->leaf_tables && // 3
642
session->lex->sql_command == SQLCOM_SELECT) // *
644
if (in_subs->is_top_level_item() && // 4
645
!in_subs->is_correlated && // 5
646
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
647
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
650
Item_subselect::trans_res trans_res;
651
if ((trans_res= subselect->select_transformer(this)) !=
652
Item_subselect::RES_OK)
654
return((trans_res == Item_subselect::RES_ERROR));
663
for (ord= order; ord; ord= ord->next)
665
Item *item= *ord->item;
666
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
667
item->split_sum_func(session, ref_pointer_array, all_fields);
671
if (having && having->with_sum_func)
672
having->split_sum_func(session, ref_pointer_array, all_fields,
674
if (select_lex->inner_sum_func_list)
676
Item_sum *end=select_lex->inner_sum_func_list;
677
Item_sum *item_sum= end;
680
item_sum= item_sum->next;
681
item_sum->split_sum_func(session, ref_pointer_array,
682
all_fields, item_sum->ref_by, false);
683
} while (item_sum != end);
686
if (select_lex->inner_refs_list.elements &&
687
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
691
Check if there are references to un-aggregated columns when computing
692
aggregate functions with implicit grouping (there is no GROUP BY).
694
MODE_ONLY_FULL_GROUP_BY is enabled here by default
696
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
698
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
699
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
703
/* Caclulate the number of groups */
705
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
710
goto err; /* purecov: inspected */
712
if (result && result->prepare(fields_list, unit_arg))
713
goto err; /* purecov: inspected */
715
/* Init join struct */
716
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
717
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
718
this->group= group_list != 0;
721
#ifdef RESTRICTED_GROUP
722
if (sum_func_count && !group_list && (func_count || field_count))
724
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
728
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
730
if (alloc_func_list())
736
return(-1); /* purecov: inspected */
741
Remove the predicates pushed down into the subquery
744
JOIN::remove_subq_pushed_predicates()
745
where IN Must be NULL
746
OUT The remaining WHERE condition, or NULL
749
Given that this join will be executed using (unique|index)_subquery,
750
without "checking NULL", remove the predicates that were pushed down
753
If the subquery compares scalar values, we can remove the condition that
754
was wrapped into trig_cond (it will be checked when needed by the subquery
757
If the subquery compares row values, we need to keep the wrapped
758
equalities in the WHERE clause: when the left (outer) tuple has both NULL
759
and non-NULL values, we'll do a full table scan and will rely on the
760
equalities corresponding to non-NULL parts of left tuple to filter out
761
non-matching records.
763
TODO: We can remove the equalities that will be guaranteed to be true by the
764
fact that subquery engine will be using index lookup. This must be done only
765
for cases where there are no conversion errors of significance, e.g. 257
766
that is searched in a byte. But this requires homogenization of the return
767
codes of all Field*::store() methods.
770
void JOIN::remove_subq_pushed_predicates(Item **where)
772
if (conds->type() == Item::FUNC_ITEM &&
773
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
774
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
775
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
776
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
777
((Item_func *)conds)->arguments()[0]))
282
786
Index lookup-based subquery: save some flags for EXPLAIN output
825
Check if the table's rowid is included in the temptable
828
sj_table_is_included()
830
join_tab The table to be checked
833
SemiJoinDuplicateElimination: check the table's rowid should be included
834
in the temptable. This is so if
836
1. The table is not embedded within some semi-join nest
837
2. The has been pulled out of a semi-join nest, or
839
3. The table is functionally dependent on some previous table
841
[4. This is also true for constant tables that can't be
842
NULL-complemented but this function is not called for such tables]
845
true - Include table's rowid
849
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
851
if (join_tab->emb_sj_nest)
854
/* Check if this table is functionally dependent on the tables that
855
are within the same outer join nest
857
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
858
if (join_tab->type == JT_EQ_REF)
860
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
862
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
864
JOIN_TAB *ref_tab= join->join_tab + idx;
865
if (embedding == ref_tab->table->pos_in_table_list->embedding)
868
/* Ok, functionally dependent */
871
/* Not functionally dependent => need to include*/
877
Setup the strategies to eliminate semi-join duplicates.
880
setup_semijoin_dups_elimination()
882
options Join options (needed to see if join buffering will be
884
no_jbuf_after Another bit of information re where join buffering will
888
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
891
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
893
2. FirstMatch (pick only the 1st matching row combination of inner tables)
894
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
895
together and picking the 1st one)
897
The join order has "duplicate-generating ranges", and every range is
898
served by one strategy or a combination of FirstMatch with with some
901
"Duplicate-generating range" is defined as a range within the join order
902
that contains all of the inner tables of a semi-join. All ranges must be
903
disjoint, if tables of several semi-joins are interleaved, then the ranges
904
are joined together, which is equivalent to converting
905
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
907
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
910
Applicability conditions are as follows:
912
DuplicateWeedout strategy
913
~~~~~~~~~~~~~~~~~~~~~~~~~
915
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
916
+------+ +=========================+ +---+
919
(1) - Prefix of OuterTables (those that participate in
920
IN-equality and/or are correlated with subquery) and outer
921
Noncorrelated Tables.
922
(2) - The handled range. The range starts with the first sj-inner
923
table, and covers all sj-inner and outer tables
924
Within the range, Inner, Outer, outer Noncorrelated tables
925
may follow in any order.
926
(3) - The suffix of outer Noncorrelated tables.
931
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
932
+------+ +==================+ +---+
935
(1) - Prefix of outer and non-correlated tables
936
(2) - The handled range, which may contain only inner and
937
non-correlated tables.
938
(3) - The suffix of outer Noncorrelated tables.
943
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
944
+--------+ +===========+ +=============+ +------+
947
(1) - Prefix that may contain any outer tables. The prefix must contain
948
all the non-trivially correlated outer tables. (non-trivially means
949
that the correlation is not just through the IN-equality).
951
(2) - Inner table for which the InsideOut scan is performed.
953
(3) - The remainder of the duplicate-generating range. It is served by
954
application of FirstMatch strategy, with the exception that
955
outer IN-correlated tables are considered to be non-correlated.
957
(4) - THe suffix of outer and outer non-correlated tables.
959
If several strategies are applicable, their relative priorities are:
964
This function walks over the join order and sets up the strategies by
965
setting appropriate members in join_tab structures.
969
true Out of memory error
973
int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
975
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
978
0 - invalid (EOF marker),
980
2 - Temptable (maybe confluent),
981
3 - Temptable with join buffering
984
uint32_t start_idx; /* Left range bound */
985
uint32_t end_idx; /* Right range bound */
987
For Temptable strategy: Bitmap of all outer and correlated tables from
988
all involved join nests.
990
table_map outer_tables;
991
} dups_ranges [MAX_TABLES];
993
TableList *emb_insideout_nest= NULL;
994
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
995
tables) whose ranges we're in */
996
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
997
table_map range_start_map= 0; /* table_map at current range start */
998
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
1003
First pass: locate the duplicate-generating ranges and pick the strategies.
1005
for (i=join->const_tables ; i < join->tables ; i++)
1007
JOIN_TAB *tab=join->join_tab+i;
1008
Table *table=tab->table;
1009
cur_map |= table->map;
1011
if (tab->emb_sj_nest) // Encountered an sj-inner table
1015
dups_ranges[cur_range].start_idx= i;
1016
range_start_map= cur_map & ~table->map;
1018
Remember if this is a possible start of range that is covered by
1019
the InsideOut strategy (the reason that it is not covered could
1020
be that it overlaps with anther semi-join's range. we don't
1021
support InsideOut for joined ranges)
1023
if (join->best_positions[i].use_insideout_scan)
1024
emb_insideout_nest= tab->emb_sj_nest;
1027
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
1028
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
1030
if (tab->emb_sj_nest != emb_insideout_nest)
1033
Two different semi-joins interleave. This cannot be handled by
1036
emb_insideout_nest= NULL;
1040
if (emb_sj_map) /* We're in duplicate-generating range */
1042
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
1043
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
1044
i <= no_jbuf_after && !dealing_with_jbuf)
1047
This table uses join buffering, which makes use of FirstMatch or
1048
InsideOut strategies impossible for the current and (we assume)
1049
preceding duplicate-producing ranges.
1050
That is, for the join order:
1052
x x [ x x] x [x x x] x [x x X* x] x
1054
+-----+ +-----+ | join buffering use
1057
we'll have to remove r1 and r2 and use duplicate-elimination
1058
strategy that spans all the tables, starting from the very 1st
1061
dealing_with_jbuf= true;
1062
emb_insideout_nest= false;
1065
Absorb all preceding duplicate-eliminating ranges. Their strategies
1068
for (int prev_range= 0; prev_range < cur_range; prev_range++)
1070
dups_ranges[cur_range].outer_tables |=
1071
dups_ranges[prev_range].outer_tables;
1073
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
1074
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
1079
Check if we are at the end of duplicate-producing range. We are if
1081
1. It's an InsideOut range (which presumes all correlated tables are
1082
in the prefix), and all inner tables are in the join order prefix,
1084
2. It's a DuplicateElimination range (possibly covering several
1085
SJ-nests), and all inner, outer, and correlated tables of all
1086
sj-nests are in the join order prefix.
1088
bool end_of_range= false;
1089
if (emb_insideout_nest &&
1090
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
1092
/* Save that this range is handled with InsideOut: */
1093
dups_ranges[cur_range].strategy= 1;
1096
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
1099
This is a complete range to be handled with either DuplicateWeedout
1102
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
1104
This will hold tables from within the range that need to be put
1105
into the join buffer before we can use the FirstMatch on its tail.
1107
dups_ranges[cur_range].outer_tables= emb_outer_tables &
1114
dups_ranges[cur_range].end_idx= i+1;
1115
emb_sj_map= emb_outer_tables= 0;
1116
emb_insideout_nest= NULL;
1117
dealing_with_jbuf= false;
1118
dups_ranges[++cur_range].strategy= 0;
1123
Session *session= join->session;
1124
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
1126
Second pass: setup the chosen strategies
1128
for (int j= 0; j < cur_range; j++)
1130
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
1132
if (dups_ranges[j].strategy == 1) // InsideOut strategy
1134
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
1137
else // DuplicateWeedout strategy
1139
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
1140
table_map weed_cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
1141
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
1142
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
1143
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
1144
uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
1145
JOIN_TAB *last_outer_tab= tab - 1;
1147
Walk through the range and remember
1148
- tables that need their rowids to be put into temptable
1149
- the last outer table
1151
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1153
if (sj_table_is_included(join, tab))
1155
last_tab->join_tab= tab;
1156
last_tab->rowid_offset= jt_rowid_offset;
1157
jt_rowid_offset += tab->table->file->ref_length;
1158
if (tab->table->maybe_null)
1160
last_tab->null_byte= jt_null_bits / 8;
1161
last_tab->null_bit= jt_null_bits++;
1164
tab->table->prepare_for_position();
1165
tab->rowid_keep_flags= rowid_keep_flags;
1167
weed_cur_map |= tab->table->map;
1168
if (!tab->emb_sj_nest && bitmap_covers(weed_cur_map,
1169
dups_ranges[j].outer_tables))
1170
last_outer_tab= tab;
1173
if (jt_rowid_offset) /* Temptable has at least one rowid */
1175
SJ_TMP_TABLE *sjtbl;
1176
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
1177
if (!(sjtbl= (SJ_TMP_TABLE*)session->alloc(sizeof(SJ_TMP_TABLE))) ||
1178
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) session->alloc(tabs_size)))
1180
memcpy(sjtbl->tabs, sjtabs, tabs_size);
1181
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
1182
sjtbl->rowid_len= jt_rowid_offset;
1183
sjtbl->null_bits= jt_null_bits;
1184
sjtbl->null_bytes= (jt_null_bits + 7)/8;
1186
*next_sjtbl_ptr= sjtbl;
1187
next_sjtbl_ptr= &(sjtbl->next);
1191
create_duplicate_weedout_tmp_table(session,
1196
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
1197
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
1199
tab= last_outer_tab + 1;
1200
jump_to= last_outer_tab;
1203
/* Create the FirstMatch tail */
1204
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1206
if (tab->emb_sj_nest)
1207
tab->do_firstmatch= jump_to;
1216
static void cleanup_sj_tmp_tables(JOIN *join)
1218
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
1219
sj_tbl= sj_tbl->next)
1221
if (sj_tbl->tmp_table)
1223
sj_tbl->tmp_table->free_tmp_table(join->session);
1226
join->sj_tmp_tables= NULL;
1229
uint32_t make_join_orderinfo(JOIN *join);
1232
global select optimisation.
1235
error code saved in field 'error'
1246
// to prevent double initialization on EXPLAIN
1251
session->set_proc_info("optimizing");
1252
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
1253
unit->select_limit_cnt);
1254
/* select_limit is used to decide if we are likely to scan the whole table */
1255
select_limit= unit->select_limit_cnt;
1256
if (having || (select_options & OPTION_FOUND_ROWS))
1257
select_limit= HA_POS_ERROR;
1258
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
1259
// Ignore errors of execution if option IGNORE present
1260
if (session->lex->ignore)
1261
session->lex->current_select->no_error= 1;
1263
#ifdef HAVE_REF_TO_FIELDS // Not done yet
1264
/* Add HAVING to WHERE if possible */
1265
if (having && !group_list && !sum_func_count)
1272
else if ((conds=new Item_cond_and(conds,having)))
1275
Item_cond_and can't be fixed after creation, so we do not check
1278
conds->fix_fields(session, &conds);
1279
conds->change_ref_to_fields(session, tables_list);
1280
conds->top_level_item();
1286
/* Convert all outer joins to inner joins if possible */
1287
conds= simplify_joins(this, join_list, conds, true, false);
1288
build_bitmap_for_nested_joins(join_list, 0);
1290
conds= optimize_cond(this, conds, join_list, &cond_value);
1291
if (session->is_error())
1298
having= optimize_cond(this, having, join_list, &having_value);
1299
if (session->is_error())
1304
if (select_lex->where)
1305
select_lex->cond_value= cond_value;
1306
if (select_lex->having)
1307
select_lex->having_value= having_value;
1309
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
1310
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
1311
{ /* Impossible cond */
1312
zero_result_cause= having_value == Item::COND_FALSE ?
1313
"Impossible HAVING" : "Impossible WHERE";
1319
/* Optimize count(*), cmin() and cmax() */
1320
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
1324
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
1325
to the WHERE conditions,
1326
or 1 if all items were resolved,
1327
or 0, or an error number HA_ERR_...
1329
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
1331
if (res == HA_ERR_KEY_NOT_FOUND)
1333
zero_result_cause= "No matching min/max row";
1344
zero_result_cause= "No matching min/max row";
1348
zero_result_cause= "Select tables optimized away";
1349
tables_list= 0; // All tables resolved
1351
Extract all table-independent conditions and replace the WHERE
1352
clause with them. All other conditions were computed by opt_sum_query
1353
and the MIN/MAX/COUNT function(s) have been replaced by constants,
1354
so there is no need to compute the whole WHERE clause again.
1355
Notice that make_cond_for_table() will always succeed to remove all
1356
computed conditions, because opt_sum_query() is applicable only to
1358
Preserve conditions for EXPLAIN.
1360
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
1362
COND *table_independent_conds=
1363
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
1364
conds= table_independent_conds;
1373
error= -1; // Error is sent to client
1374
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
1376
/* Calculate how to do the join */
1377
session->set_proc_info("statistics");
1378
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
1379
session->is_fatal_error)
1384
/* Remove distinct if only const tables */
1385
select_distinct= select_distinct && (const_tables != tables);
1386
session->set_proc_info("preparing");
1387
if (result->initialize_tables(this))
1389
return(1); // error == -1
1391
if (const_table_map != found_const_table_map &&
1392
!(select_options & SELECT_DESCRIBE) &&
1394
!(conds->used_tables() & RAND_TABLE_BIT) ||
1395
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
1397
zero_result_cause= "no matching row in const table";
1401
if (!(session->options & OPTION_BIG_SELECTS) &&
1402
best_read > (double) session->variables.max_join_size &&
1403
!(select_options & SELECT_DESCRIBE))
1404
{ /* purecov: inspected */
1405
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
1409
if (const_tables && !session->locked_tables &&
1410
!(select_options & SELECT_NO_UNLOCK))
1411
mysql_unlock_some_tables(session, table, const_tables);
1412
if (!conds && outer_join)
1414
/* Handle the case where we have an OUTER JOIN without a WHERE */
1415
conds=new Item_int((int64_t) 1,1); // Always true
1417
select= make_select(*table, const_table_map,
1418
const_table_map, conds, 1, &error);
1420
{ /* purecov: inspected */
1421
error= -1; /* purecov: inspected */
1425
reset_nj_counters(join_list);
1426
make_outerjoin_info(this);
1429
Among the equal fields belonging to the same multiple equality
1430
choose the one that is to be retrieved first and substitute
1431
all references to these in where condition for a reference for
1436
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
1437
conds->update_used_tables();
1441
Permorm the the optimization on fields evaluation mentioned above
1442
for all on expressions.
1444
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
1446
if (*tab->on_expr_ref)
1448
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
1451
(*tab->on_expr_ref)->update_used_tables();
1455
if (conds &&!outer_join && const_table_map != found_const_table_map &&
1456
(select_options & SELECT_DESCRIBE) &&
1457
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
1459
conds=new Item_int((int64_t) 0,1); // Always false
1461
if (make_join_select(this, select, conds))
1464
"Impossible WHERE noticed after reading const tables";
1465
return(0); // error == 0
1468
error= -1; /* if goto err */
1470
/* Optimize distinct away if possible */
1472
order_st *org_order= order;
1473
order=remove_const(this, order,conds,1, &simple_order);
1474
if (session->is_error())
1481
If we are using order_st BY NULL or order_st BY const_expression,
1482
return result in any order (even if we are using a GROUP BY)
1484
if (!order && org_order)
1488
Check if we can optimize away GROUP BY/DISTINCT.
1489
We can do that if there are no aggregate functions, the
1490
fields in DISTINCT clause (if present) and/or columns in GROUP BY
1491
(if present) contain direct references to all key parts of
1492
an unique index (in whatever order) and if the key parts of the
1493
unique index cannot contain NULLs.
1494
Note that the unique keys for DISTINCT and GROUP BY should not
1495
be the same (as long as they are unique).
1497
The FROM clause must contain a single non-constant table.
1499
if (tables - const_tables == 1 && (group_list || select_distinct) &&
1500
!tmp_table_param.sum_func_count &&
1501
(!join_tab[const_tables].select ||
1502
!join_tab[const_tables].select->quick ||
1503
join_tab[const_tables].select->quick->get_type() !=
1504
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
1507
list_contains_unique_index(join_tab[const_tables].table,
1508
find_field_in_order_list,
1509
(void *) group_list))
1512
We have found that grouping can be removed since groups correspond to
1513
only one row anyway, but we still have to guarantee correct result
1514
order. The line below effectively rewrites the query from GROUP BY
1515
<fields> to order_st BY <fields>. There are two exceptions:
1516
- if skip_sort_order is set (see above), then we can simply skip
1518
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
1519
with the GROUP BY ones, i.e. either one is a prefix of another.
1520
We only check if the order_st BY is a prefix of GROUP BY. In this case
1521
test_if_subpart() copies the ASC/DESC attributes from the original
1523
If GROUP BY is a prefix of order_st BY, then it is safe to leave
1526
if (!order || test_if_subpart(group_list, order))
1527
order= skip_sort_order ? 0 : group_list;
1529
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
1530
rewritten to IGNORE INDEX FOR order_st BY(fields).
1532
join_tab->table->keys_in_use_for_order_by=
1533
join_tab->table->keys_in_use_for_group_by;
1537
if (select_distinct &&
1538
list_contains_unique_index(join_tab[const_tables].table,
1539
find_field_in_item_list,
1540
(void *) &fields_list))
1545
if (group_list || tmp_table_param.sum_func_count)
1547
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
1550
else if (select_distinct && tables - const_tables == 1)
1553
We are only using one table. In this case we change DISTINCT to a
1555
- The GROUP BY can be done through indexes (no sort) and the order_st
1556
BY only uses selected fields.
1557
(In this case we can later optimize away GROUP BY and order_st BY)
1558
- We are scanning the whole table without LIMIT
1560
- We are using CALC_FOUND_ROWS
1561
- We are using an order_st BY that can't be optimized away.
1563
We don't want to use this optimization when we are using LIMIT
1564
because in this case we can just create a temporary table that
1565
holds LIMIT rows and stop when this table is full.
1567
JOIN_TAB *tab= &join_tab[const_tables];
1568
bool all_order_fields_used;
1570
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
1571
&tab->table->keys_in_use_for_order_by);
1572
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
1573
order, fields_list, all_fields,
1574
&all_order_fields_used)))
1576
bool skip_group= (skip_sort_order &&
1577
test_if_skip_sort_order(tab, group_list, select_limit, 1,
1578
&tab->table->keys_in_use_for_group_by) != 0);
1579
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
1580
if ((skip_group && all_order_fields_used) ||
1581
select_limit == HA_POS_ERROR ||
1582
(order && !skip_sort_order))
1584
/* Change DISTINCT to GROUP BY */
1587
if (all_order_fields_used)
1589
if (order && skip_sort_order)
1592
Force MySQL to read the table in sorted order to get result in
1595
tmp_table_param.quick_group=0;
1599
group=1; // For end_write_group
1604
else if (session->is_fatal_error) // End of memory
1609
order_st *old_group_list;
1610
group_list= remove_const(this, (old_group_list= group_list), conds,
1611
rollup.state == ROLLUP::STATE_NONE,
1613
if (session->is_error())
1618
if (old_group_list && !group_list)
1621
if (!group_list && group)
1623
order=0; // The output has only one row
1625
select_distinct= 0; // No need in distinct for 1 row
1626
group_optimized_away= 1;
1629
calc_group_buffer(this, group_list);
1630
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
1632
if (test_if_subpart(group_list, order) ||
1633
(!group_list && tmp_table_param.sum_func_count))
1636
// Can't use sort on head table if using row cache
1646
Check if we need to create a temporary table.
1647
This has to be done if all tables are not already read (const tables)
1648
and one of the following conditions holds:
1649
- We are using DISTINCT (simple distinct's are already optimized away)
1650
- We are using an order_st BY or GROUP BY on fields not in the first table
1651
- We are using different order_st BY and GROUP BY orders
1652
- The user wants us to buffer the result.
1654
need_tmp= (const_tables != tables &&
1655
((select_distinct || !simple_order || !simple_group) ||
1656
(group_list && order) ||
1657
test(select_options & OPTION_BUFFER_RESULT)));
1659
uint32_t no_jbuf_after= make_join_orderinfo(this);
1660
uint64_t select_opts_for_readinfo=
1661
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
1663
sj_tmp_tables= NULL;
1664
if (!select_lex->sj_nests.is_empty())
1665
setup_semijoin_dups_elimination(this, select_opts_for_readinfo,
1668
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1669
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1672
/* Create all structures needed for materialized subquery execution. */
1673
if (setup_subquery_materialization())
1677
is this simple IN subquery?
1679
if (!group_list && !order &&
1680
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1681
tables == 1 && conds &&
1687
if (join_tab[0].type == JT_EQ_REF &&
1688
join_tab[0].ref.items[0]->name == in_left_expr_name)
1690
remove_subq_pushed_predicates(&where);
1691
save_index_subquery_explain_info(join_tab, where);
1692
join_tab[0].type= JT_UNIQUE_SUBQUERY;
1696
subselect_uniquesubquery_engine(session,
1701
else if (join_tab[0].type == JT_REF &&
1702
join_tab[0].ref.items[0]->name == in_left_expr_name)
1704
remove_subq_pushed_predicates(&where);
1705
save_index_subquery_explain_info(join_tab, where);
1706
join_tab[0].type= JT_INDEX_SUBQUERY;
1710
subselect_indexsubquery_engine(session,
1717
} else if (join_tab[0].type == JT_REF_OR_NULL &&
1718
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1719
having->name == in_having_cond)
1721
join_tab[0].type= JT_INDEX_SUBQUERY;
1723
conds= remove_additional_cond(conds);
1724
save_index_subquery_explain_info(join_tab, conds);
1726
change_engine(new subselect_indexsubquery_engine(session,
1736
Need to tell handlers that to play it safe, it should fetch all
1737
columns of the primary key of the tables: this is because MySQL may
1738
build row pointers for the rows, and for all columns of the primary key
1739
the read set has not necessarily been set by the server code.
1741
if (need_tmp || select_distinct || group_list || order)
1743
for (uint32_t i = const_tables; i < tables; i++)
1744
join_tab[i].table->prepare_for_position();
1747
if (const_tables != tables)
1750
Because filesort always does a full table scan or a quick range scan
1751
we must add the removed reference to the select for the table.
1752
We only need to do this when we have a simple_order or simple_group
1753
as in other cases the join is done before the sort.
1755
if ((order || group_list) &&
1756
(join_tab[const_tables].type != JT_ALL) &&
1757
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
1758
((order && simple_order) || (group_list && simple_group)))
1760
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
1765
if (!(select_options & SELECT_BIG_RESULT) &&
1768
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1769
unit->select_limit_cnt, 0,
1770
&join_tab[const_tables].table->
1771
keys_in_use_for_group_by))) ||
1773
tmp_table_param.quick_group)
1775
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1780
Force using of tmp table if sorting by a SP or UDF function due to
1781
their expensive and probably non-deterministic nature.
1783
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1785
Item *item= *tmp_order->item;
1786
if (item->is_expensive())
1788
/* Force tmp table without sort */
1789
need_tmp=1; simple_order=simple_group=0;
1797
if (select_options & SELECT_DESCRIBE)
1805
The loose index scan access method guarantees that all grouping or
1806
duplicate row elimination (for distinct) is already performed
1807
during data retrieval, and that all MIN/MAX functions are already
1808
computed for each group. Thus all MIN/MAX functions should be
1809
treated as regular functions, and there is no need to perform
1810
grouping in the main execution loop.
1811
Notice that currently loose index scan is applicable only for
1812
single table queries, thus it is sufficient to test only the first
1813
join_tab element of the plan for its access method.
1815
if (join_tab->is_using_loose_index_scan())
1816
tmp_table_param.precomputed_group_by= true;
1818
/* Create a tmp table if distinct or if the sort is too complicated */
1821
session->set_proc_info("Creating tmp table");
1823
init_items_ref_array();
1825
tmp_table_param.hidden_field_count= (all_fields.elements -
1826
fields_list.elements);
1827
order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1830
Pushing LIMIT to the temporary table creation is not applicable
1831
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1832
there are aggregate functions, because in all these cases we need
1835
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1837
!session->lex->current_select->with_sum_func) ?
1838
select_limit : HA_POS_ERROR;
1840
if (!(exec_tmp_table1=
1841
create_tmp_table(session, &tmp_table_param, all_fields,
1843
group_list ? 0 : select_distinct,
1844
group_list && simple_group,
1853
We don't have to store rows in temp table that doesn't match HAVING if:
1854
- we are sorting the table and writing complete group rows to the
1856
- We are using DISTINCT without resolving the distinct as a GROUP BY
1859
If having is not handled here, it will be checked before the row
1860
is sent to the client.
1863
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1866
/* if group or order on first table, sort first */
1867
if (group_list && simple_group)
1869
session->set_proc_info("Sorting for group");
1870
if (create_sort_index(session, this, group_list,
1871
HA_POS_ERROR, HA_POS_ERROR, false) ||
1872
alloc_group_fields(this, group_list) ||
1873
make_sum_func_list(all_fields, fields_list, 1) ||
1874
setup_sum_funcs(session, sum_funcs))
1882
if (make_sum_func_list(all_fields, fields_list, 0) ||
1883
setup_sum_funcs(session, sum_funcs))
1888
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1890
session->set_proc_info("Sorting for order");
1891
if (create_sort_index(session, this, order,
1892
HA_POS_ERROR, HA_POS_ERROR, true))
1901
Optimize distinct when used on some of the tables
1902
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1903
In this case we can stop scanning t2 when we have found one t1.a
1906
if (exec_tmp_table1->distinct)
1908
table_map used_tables= session->used_tables;
1909
JOIN_TAB *last_join_tab= join_tab+tables-1;
1912
if (used_tables & last_join_tab->table->map)
1914
last_join_tab->not_used_in_distinct=1;
1915
} while (last_join_tab-- != join_tab);
1916
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1917
if (order && skip_sort_order)
1919
/* Should always succeed */
1920
if (test_if_skip_sort_order(&join_tab[const_tables],
1921
order, unit->select_limit_cnt, 0,
1922
&join_tab[const_tables].table->
1923
keys_in_use_for_order_by))
1929
If this join belongs to an uncacheable subquery save
1932
if (select_lex->uncacheable && !is_top_level_join() &&
1933
init_save_join_tab())
1934
return(-1); /* purecov: inspected */
1943
Restore values in temporary join.
1945
void JOIN::restore_tmp()
1947
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1954
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1955
select_lex->offset_limit->val_uint() :
1960
if (exec_tmp_table1)
1962
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1963
exec_tmp_table1->file->ha_delete_all_rows();
1964
free_io_cache(exec_tmp_table1);
1965
filesort_free_buffers(exec_tmp_table1,0);
1967
if (exec_tmp_table2)
1969
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1970
exec_tmp_table2->file->ha_delete_all_rows();
1971
free_io_cache(exec_tmp_table2);
1972
filesort_free_buffers(exec_tmp_table2,0);
1975
set_items_ref_array(items0);
1978
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1983
/* Reset of sum functions */
1986
Item_sum *func, **func_ptr= sum_funcs;
1987
while ((func= *(func_ptr++)))
1995
@brief Save the original join layout
1997
@details Saves the original join layout so it can be reused in
1998
re-execution and for EXPLAIN.
2000
@return Operation status
2002
@retval 1 error occurred.
2006
JOIN::init_save_join_tab()
2008
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
2009
return 1; /* purecov: inspected */
2010
error= 0; // Ensure that tmp_join.error= 0
2017
JOIN::save_join_tab()
2019
if (!join_tab_save && select_lex->master_unit()->uncacheable)
2021
if (!(join_tab_save= (JOIN_TAB*)session->memdup((unsigned char*) join_tab,
2022
sizeof(JOIN_TAB) * tables)))
2033
Note, that create_sort_index calls test_if_skip_sort_order and may
2034
finally replace sorting with index scan if there is a LIMIT clause in
2035
the query. It's never shown in EXPLAIN!
2038
When can we have here session->net.report_error not zero?
2043
List<Item> *columns_list= &fields_list;
2046
session->set_proc_info("executing");
2049
if (!tables_list && (tables || !select_lex->with_sum_func))
2051
/* Only test of functions */
2052
if (select_options & SELECT_DESCRIBE)
2053
select_describe(this, false, false, false,
2054
(zero_result_cause?zero_result_cause:"No tables used"));
2057
result->send_fields(*columns_list,
2058
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2060
We have to test for 'conds' here as the WHERE may not be constant
2061
even if we don't have any tables for prepared statements or if
2062
conds uses something like 'rand()'.
2064
if (cond_value != Item::COND_FALSE &&
2065
(!conds || conds->val_int()) &&
2066
(!having || having->val_int()))
2068
if (do_send_rows && result->send_data(fields_list))
2072
error= (int) result->send_eof();
2073
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
2078
error= (int) result->send_eof();
2082
/* Single select (without union) always returns 0 or 1 row */
2083
session->limit_found_rows= send_records;
2084
session->examined_row_count= 0;
2088
Don't reset the found rows count if there're no tables as
2089
FOUND_ROWS() may be called. Never reset the examined row count here.
2090
It must be accumulated from all join iterations of all join parts.
2093
session->limit_found_rows= 0;
2095
if (zero_result_cause)
2097
(void) return_zero_rows(this, result, select_lex->leaf_tables,
2099
send_row_on_empty_set(),
2106
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) &&
2107
get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
2110
if (select_options & SELECT_DESCRIBE)
2113
Check if we managed to optimize order_st BY away and don't use temporary
2114
table to resolve order_st BY: in that case, we only may need to do
2115
filesort for GROUP BY.
2117
if (!order && !no_order && (!skip_sort_order || !need_tmp))
2120
Reset 'order' to 'group_list' and reinit variables describing
2124
simple_order= simple_group;
2128
(order != group_list || !(select_options & SELECT_BIG_RESULT)) &&
2129
(const_tables == tables ||
2130
((simple_order || skip_sort_order) &&
2131
test_if_skip_sort_order(&join_tab[const_tables], order,
2133
&join_tab[const_tables].table->
2134
keys_in_use_for_query))))
2137
select_describe(this, need_tmp,
2138
order != 0 && !skip_sort_order,
2140
!tables ? "No tables used" : NULL);
2144
JOIN *curr_join= this;
2145
List<Item> *curr_all_fields= &all_fields;
2146
List<Item> *curr_fields_list= &fields_list;
2147
Table *curr_tmp_table= 0;
2149
Initialize examined rows here because the values from all join parts
2150
must be accumulated in examined_row_count. Hence every join
2151
iteration must count from zero.
2153
curr_join->examined_rows= 0;
2155
/* Create a tmp table if distinct or if the sort is too complicated */
2161
We are in a non cacheable sub query. Get the saved join structure
2163
(curr_join may have been modified during last exection and we need
2166
curr_join= tmp_join;
2168
curr_tmp_table= exec_tmp_table1;
2170
/* Copy data to the temporary table */
2171
session->set_proc_info("Copying to tmp table");
2172
if (!curr_join->sort_and_group &&
2173
curr_join->const_tables != curr_join->tables)
2174
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2175
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2180
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
2182
if (curr_join->having)
2183
curr_join->having= curr_join->tmp_having= 0; // Allready done
2185
/* Change sum_fields reference to calculated fields in tmp_table */
2186
curr_join->all_fields= *curr_all_fields;
2189
items1= items0 + all_fields.elements;
2190
if (sort_and_group || curr_tmp_table->group)
2192
if (change_to_use_tmp_fields(session, items1,
2193
tmp_fields_list1, tmp_all_fields1,
2194
fields_list.elements, all_fields))
2199
if (change_refs_to_tmp_fields(session, items1,
2200
tmp_fields_list1, tmp_all_fields1,
2201
fields_list.elements, all_fields))
2204
curr_join->tmp_all_fields1= tmp_all_fields1;
2205
curr_join->tmp_fields_list1= tmp_fields_list1;
2206
curr_join->items1= items1;
2208
curr_all_fields= &tmp_all_fields1;
2209
curr_fields_list= &tmp_fields_list1;
2210
curr_join->set_items_ref_array(items1);
2212
if (sort_and_group || curr_tmp_table->group)
2214
curr_join->tmp_table_param.field_count+=
2215
curr_join->tmp_table_param.sum_func_count+
2216
curr_join->tmp_table_param.func_count;
2217
curr_join->tmp_table_param.sum_func_count=
2218
curr_join->tmp_table_param.func_count= 0;
2222
curr_join->tmp_table_param.field_count+=
2223
curr_join->tmp_table_param.func_count;
2224
curr_join->tmp_table_param.func_count= 0;
2227
if (curr_tmp_table->group)
2228
{ // Already grouped
2229
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
2230
curr_join->order= curr_join->group_list; /* order by group */
2231
curr_join->group_list= 0;
2235
If we have different sort & group then we must sort the data by group
2236
and copy it to another tmp table
2237
This code is also used if we are using distinct something
2238
we haven't been able to store in the temporary table yet
2239
like SEC_TO_TIME(SUM(...)).
2242
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))
2243
{ /* Must copy to another table */
2244
/* Free first data from old join */
2245
curr_join->join_free();
2246
if (make_simple_join(curr_join, curr_tmp_table))
2248
calc_group_buffer(curr_join, group_list);
2249
count_field_types(select_lex, &curr_join->tmp_table_param,
2250
curr_join->tmp_all_fields1,
2251
curr_join->select_distinct && !curr_join->group_list);
2252
curr_join->tmp_table_param.hidden_field_count=
2253
(curr_join->tmp_all_fields1.elements-
2254
curr_join->tmp_fields_list1.elements);
2257
if (exec_tmp_table2)
2258
curr_tmp_table= exec_tmp_table2;
2261
/* group data to new table */
2264
If the access method is loose index scan then all MIN/MAX
2265
functions are precomputed, and should be treated as regular
2266
functions. See extended comment in JOIN::exec.
2268
if (curr_join->join_tab->is_using_loose_index_scan())
2269
curr_join->tmp_table_param.precomputed_group_by= true;
2271
if (!(curr_tmp_table=
2272
exec_tmp_table2= create_tmp_table(session,
2273
&curr_join->tmp_table_param,
2276
curr_join->select_distinct &&
2277
!curr_join->group_list,
2278
1, curr_join->select_options,
2282
curr_join->exec_tmp_table2= exec_tmp_table2;
2284
if (curr_join->group_list)
2286
session->set_proc_info("Creating sort index");
2287
if (curr_join->join_tab == join_tab && save_join_tab())
2291
if (create_sort_index(session, curr_join, curr_join->group_list,
2292
HA_POS_ERROR, HA_POS_ERROR, false) ||
2293
make_group_fields(this, curr_join))
2297
sortorder= curr_join->sortorder;
2300
session->set_proc_info("Copying to group table");
2302
if (curr_join != this)
2306
curr_join->sum_funcs= sum_funcs2;
2307
curr_join->sum_funcs_end= sum_funcs_end2;
2311
curr_join->alloc_func_list();
2312
sum_funcs2= curr_join->sum_funcs;
2313
sum_funcs_end2= curr_join->sum_funcs_end;
2316
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2319
curr_join->group_list= 0;
2320
if (!curr_join->sort_and_group &&
2321
curr_join->const_tables != curr_join->tables)
2322
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2323
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2324
(tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2329
end_read_record(&curr_join->join_tab->read_record);
2330
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
2331
curr_join->join_tab[0].table= 0; // Table is freed
2333
// No sum funcs anymore
2336
items2= items1 + all_fields.elements;
2337
if (change_to_use_tmp_fields(session, items2,
2338
tmp_fields_list2, tmp_all_fields2,
2339
fields_list.elements, tmp_all_fields1))
2341
curr_join->tmp_fields_list2= tmp_fields_list2;
2342
curr_join->tmp_all_fields2= tmp_all_fields2;
2344
curr_fields_list= &curr_join->tmp_fields_list2;
2345
curr_all_fields= &curr_join->tmp_all_fields2;
2346
curr_join->set_items_ref_array(items2);
2347
curr_join->tmp_table_param.field_count+=
2348
curr_join->tmp_table_param.sum_func_count;
2349
curr_join->tmp_table_param.sum_func_count= 0;
2351
if (curr_tmp_table->distinct)
2352
curr_join->select_distinct=0; /* Each row is unique */
2354
curr_join->join_free(); /* Free quick selects */
2355
if (curr_join->select_distinct && ! curr_join->group_list)
2357
session->set_proc_info("Removing duplicates");
2358
if (curr_join->tmp_having)
2359
curr_join->tmp_having->update_used_tables();
2360
if (remove_duplicates(curr_join, curr_tmp_table,
2361
*curr_fields_list, curr_join->tmp_having))
2363
curr_join->tmp_having=0;
2364
curr_join->select_distinct=0;
2366
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
2367
if (make_simple_join(curr_join, curr_tmp_table))
2369
calc_group_buffer(curr_join, curr_join->group_list);
2370
count_field_types(select_lex, &curr_join->tmp_table_param,
2371
*curr_all_fields, 0);
2375
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
2377
if (make_group_fields(this, curr_join))
2384
init_items_ref_array();
2385
items3= ref_pointer_array + (all_fields.elements*4);
2386
setup_copy_fields(session, &curr_join->tmp_table_param,
2387
items3, tmp_fields_list3, tmp_all_fields3,
2388
curr_fields_list->elements, *curr_all_fields);
2389
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
2390
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
2391
tmp_table_param.save_copy_field_end=
2392
curr_join->tmp_table_param.copy_field_end;
2393
curr_join->tmp_all_fields3= tmp_all_fields3;
2394
curr_join->tmp_fields_list3= tmp_fields_list3;
2398
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
2399
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
2400
curr_join->tmp_table_param.copy_field_end=
2401
tmp_table_param.save_copy_field_end;
2403
curr_fields_list= &tmp_fields_list3;
2404
curr_all_fields= &tmp_all_fields3;
2405
curr_join->set_items_ref_array(items3);
2407
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2409
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2410
session->is_fatal_error)
2413
if (curr_join->group_list || curr_join->order)
2415
session->set_proc_info("Sorting result");
2416
/* If we have already done the group, add HAVING to sorted table */
2417
if (curr_join->tmp_having && ! curr_join->group_list &&
2418
! curr_join->sort_and_group)
2420
// Some tables may have been const
2421
curr_join->tmp_having->update_used_tables();
2422
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
2423
table_map used_tables= (curr_join->const_table_map |
2424
curr_table->table->map);
2426
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having,
2429
if (sort_table_cond)
2431
if (!curr_table->select)
2432
if (!(curr_table->select= new SQL_SELECT))
2434
if (!curr_table->select->cond)
2435
curr_table->select->cond= sort_table_cond;
2436
else // This should never happen
2438
if (!(curr_table->select->cond=
2439
new Item_cond_and(curr_table->select->cond,
2443
Item_cond_and do not need fix_fields for execution, its parameters
2444
are fixed or do not need fix_fields, too
2446
curr_table->select->cond->quick_fix_field();
2448
curr_table->select_cond= curr_table->select->cond;
2449
curr_table->select_cond->top_level_item();
2450
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
2457
curr_join->select_limit= HA_POS_ERROR;
2461
We can abort sorting after session->select_limit rows if we there is no
2462
WHERE clause for any tables after the sorted one.
2464
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
2465
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
2466
for (; curr_table < end_table ; curr_table++)
2469
table->keyuse is set in the case there was an original WHERE clause
2470
on the table that was optimized away.
2472
if (curr_table->select_cond ||
2473
(curr_table->keyuse && !curr_table->first_inner))
2475
/* We have to sort all rows */
2476
curr_join->select_limit= HA_POS_ERROR;
2481
if (curr_join->join_tab == join_tab && save_join_tab())
2486
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
2487
chose FILESORT to be faster than INDEX SCAN or there is no
2488
suitable index present.
2489
Note, that create_sort_index calls test_if_skip_sort_order and may
2490
finally replace sorting with index scan if there is a LIMIT clause in
2491
the query. XXX: it's never shown in EXPLAIN!
2492
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
2494
if (create_sort_index(session, curr_join,
2495
curr_join->group_list ?
2496
curr_join->group_list : curr_join->order,
2497
curr_join->select_limit,
2498
(select_options & OPTION_FOUND_ROWS ?
2499
HA_POS_ERROR : unit->select_limit_cnt),
2500
curr_join->group_list ? true : false))
2502
sortorder= curr_join->sortorder;
2503
if (curr_join->const_tables != curr_join->tables &&
2504
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
2507
If no IO cache exists for the first table then we are using an
2508
INDEX SCAN and no filesort. Thus we should not remove the sorted
2509
attribute on the INDEX SCAN.
2515
/* XXX: When can we have here session->is_error() not zero? */
2516
if (session->is_error())
2518
error= session->is_error();
2521
curr_join->having= curr_join->tmp_having;
2522
curr_join->fields= curr_fields_list;
2525
session->set_proc_info("Sending data");
2526
result->send_fields(*curr_fields_list,
2527
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2528
error= do_select(curr_join, curr_fields_list, NULL);
2529
session->limit_found_rows= curr_join->send_records;
2532
/* Accumulate the counts from all join iterations of all join parts. */
2533
session->examined_row_count+= curr_join->examined_rows;
2536
With EXPLAIN EXTENDED we have to restore original ref_array
2537
for a derived table which is always materialized.
2538
Otherwise we would not be able to print the query correctly.
2541
(session->lex->describe & DESCRIBE_EXTENDED) &&
2542
select_lex->linkage == DERIVED_TABLE_TYPE)
2543
set_items_ref_array(items0);
2553
Return error that hold JOIN.
2559
select_lex->join= 0;
2563
if (join_tab != tmp_join->join_tab)
2565
JOIN_TAB *tab, *end;
2566
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
2569
tmp_join->tmp_join= 0;
2570
tmp_table_param.copy_field=0;
2571
return(tmp_join->destroy());
2576
if (exec_tmp_table1)
2577
exec_tmp_table1->free_tmp_table(session);
2578
if (exec_tmp_table2)
2579
exec_tmp_table2->free_tmp_table(session);
2581
delete_dynamic(&keyuse);
317
2588
An entry point to single-unit select (a select without UNION).
319
@param session thread Cursor
2590
@param session thread handler
320
2591
@param rref_pointer_array a reference to ref_pointer_array of
321
2592
the top-level select_lex for this query
322
2593
@param tables list of all tables used in this query.
452
2724
return(join->error);
455
inline Item *and_items(Item* cond, Item *item)
2728
int subq_sj_candidate_cmp(Item_in_subselect* const *el1,
2729
Item_in_subselect* const *el2)
2731
return ((*el1)->sj_convert_priority < (*el2)->sj_convert_priority) ? 1 :
2732
( ((*el1)->sj_convert_priority == (*el2)->sj_convert_priority)? 0 : -1);
2736
inline Item * and_items(Item* cond, Item *item)
457
2738
return (cond? (new Item_cond_and(cond, item)) : item);
2742
static TableList *alloc_join_nest(Session *session)
2745
if (!(tbl= (TableList*) session->calloc(ALIGN_SIZE(sizeof(TableList))+
2746
sizeof(nested_join_st))))
2748
tbl->nested_join= (nested_join_st*) ((unsigned char*)tbl +
2749
ALIGN_SIZE(sizeof(TableList)));
2754
void fix_list_after_tbl_changes(Select_Lex *new_parent, List<TableList> *tlist)
2756
List_iterator<TableList> it(*tlist);
2758
while ((table= it++))
2761
table->on_expr->fix_after_pullout(new_parent, &table->on_expr);
2762
if (table->nested_join)
2763
fix_list_after_tbl_changes(new_parent, &table->nested_join->join_list);
2769
Convert a subquery predicate into a TableList semi-join nest
2772
convert_subq_to_sj()
2773
parent_join Parent join, the one that has subq_pred in its WHERE/ON
2775
subq_pred Subquery predicate to be converted
2778
Convert a subquery predicate into a TableList semi-join nest. All the
2779
prerequisites are already checked, so the conversion is always successfull.
2781
Prepared Statements: the transformation is permanent:
2782
- Changes in TableList structures are naturally permanent
2783
- Item tree changes are performed on statement MEM_ROOT:
2784
= we activate statement MEM_ROOT
2785
= this function is called before the first fix_prepare_information
2788
This is intended because the criteria for subquery-to-sj conversion remain
2789
constant for the lifetime of the Prepared Statement.
2793
true Out of memory error
2796
bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
2798
Select_Lex *parent_lex= parent_join->select_lex;
2799
TableList *emb_tbl_nest= NULL;
2800
List<TableList> *emb_join_list= &parent_lex->top_join_list;
2801
Session *session= parent_join->session;
2804
1. Find out where to put the predicate into.
2805
Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
2807
if ((void*)subq_pred->expr_join_nest != (void*)1)
2809
if (subq_pred->expr_join_nest->nested_join)
2814
... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
2816
The sj-nest will be inserted into the brackets nest.
2818
emb_tbl_nest= subq_pred->expr_join_nest;
2819
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2821
else if (!subq_pred->expr_join_nest->outer_join)
2826
... INNER JOIN tblX ON (subquery AND whatever) ...
2828
The sj-nest will be tblX's "sibling", i.e. another child of its
2829
parent. This is ok because tblX is joined as an inner join.
2831
emb_tbl_nest= subq_pred->expr_join_nest->embedding;
2833
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2835
else if (!subq_pred->expr_join_nest->nested_join)
2837
TableList *outer_tbl= subq_pred->expr_join_nest;
2838
TableList *wrap_nest;
2842
... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
2844
we'll need to convert it into:
2846
... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
2848
|<----- wrap_nest ---->|
2850
Q: other subqueries may be pointing to this element. What to do?
2851
A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
2852
But we'll need to fix other pointers.
2853
A2: Another way: have TableList::next_ptr so the following
2854
subqueries know the table has been nested.
2855
A3: changes in the TableList::outer_join will make everything work
2858
if (!(wrap_nest= alloc_join_nest(parent_join->session)))
2862
wrap_nest->embedding= outer_tbl->embedding;
2863
wrap_nest->join_list= outer_tbl->join_list;
2864
wrap_nest->alias= (char*) "(sj-wrap)";
2866
wrap_nest->nested_join->join_list.empty();
2867
wrap_nest->nested_join->join_list.push_back(outer_tbl);
2869
outer_tbl->embedding= wrap_nest;
2870
outer_tbl->join_list= &wrap_nest->nested_join->join_list;
2873
wrap_nest will take place of outer_tbl, so move the outer join flag
2876
wrap_nest->outer_join= outer_tbl->outer_join;
2877
outer_tbl->outer_join= 0;
2879
wrap_nest->on_expr= outer_tbl->on_expr;
2880
outer_tbl->on_expr= NULL;
2882
List_iterator<TableList> li(*wrap_nest->join_list);
2886
if (tbl == outer_tbl)
2888
li.replace(wrap_nest);
2893
Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
2894
semi-join nest into it
2896
emb_join_list= &wrap_nest->nested_join->join_list;
2897
emb_tbl_nest= wrap_nest;
2902
nested_join_st *nested_join;
2903
if (!(sj_nest= alloc_join_nest(parent_join->session)))
2907
nested_join= sj_nest->nested_join;
2909
sj_nest->join_list= emb_join_list;
2910
sj_nest->embedding= emb_tbl_nest;
2911
sj_nest->alias= (char*) "(sj-nest)";
2912
/* Nests do not participate in those 'chains', so: */
2913
/* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
2914
emb_join_list->push_back(sj_nest);
2917
nested_join->used_tables and nested_join->not_null_tables are
2918
initialized in simplify_joins().
2922
2. Walk through subquery's top list and set 'embedding' to point to the
2925
Select_Lex *subq_lex= subq_pred->unit->first_select();
2926
nested_join->join_list.empty();
2927
List_iterator_fast<TableList> li(subq_lex->top_join_list);
2928
TableList *tl, *last_leaf;
2931
tl->embedding= sj_nest;
2932
tl->join_list= &nested_join->join_list;
2933
nested_join->join_list.push_back(tl);
2937
Reconnect the next_leaf chain.
2938
TODO: Do we have to put subquery's tables at the end of the chain?
2939
Inserting them at the beginning would be a bit faster.
2940
NOTE: We actually insert them at the front! That's because the order is
2941
reversed in this list.
2943
for (tl= parent_lex->leaf_tables; tl->next_leaf; tl= tl->next_leaf) {};
2944
tl->next_leaf= subq_lex->leaf_tables;
2948
Same as above for next_local chain
2949
(a theory: a next_local chain always starts with ::leaf_tables
2950
because view's tables are inserted after the view)
2952
for (tl= parent_lex->leaf_tables; tl->next_local; tl= tl->next_local) {};
2953
tl->next_local= subq_lex->leaf_tables;
2955
/* A theory: no need to re-connect the next_global chain */
2957
/* 3. Remove the original subquery predicate from the WHERE/ON */
2959
// The subqueries were replaced for Item_int(1) earlier
2960
subq_pred->exec_method= Item_in_subselect::SEMI_JOIN; // for subsequent executions
2961
/*TODO: also reset the 'with_subselect' there. */
2963
/* n. Adjust the parent_join->tables counter */
2964
uint32_t table_no= parent_join->tables;
2965
/* n. Walk through child's tables and adjust table->map */
2966
for (tl= subq_lex->leaf_tables; tl; tl= tl->next_leaf, table_no++)
2968
tl->table->tablenr= table_no;
2969
tl->table->map= ((table_map)1) << table_no;
2970
Select_Lex *old_sl= tl->select_lex;
2971
tl->select_lex= parent_join->select_lex;
2972
for(TableList *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)
2973
emb->select_lex= parent_join->select_lex;
2975
parent_join->tables += subq_lex->join->tables;
2978
Put the subquery's WHERE into semi-join's sj_on_expr
2979
Add the subquery-induced equalities too.
2981
Select_Lex *save_lex= session->lex->current_select;
2982
session->lex->current_select=subq_lex;
2983
if (!subq_pred->left_expr->fixed &&
2984
subq_pred->left_expr->fix_fields(session, &subq_pred->left_expr))
2986
session->lex->current_select=save_lex;
2988
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
2989
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables() |
2990
subq_pred->left_expr->used_tables();
2991
sj_nest->sj_on_expr= subq_lex->where;
2994
Create the IN-equalities and inject them into semi-join's ON expression.
2995
Additionally, for InsideOut strategy
2996
- Record the number of IN-equalities.
2997
- Create list of pointers to (oe1, ..., ieN). We'll need the list to
2998
see which of the expressions are bound and which are not (for those
2999
we'll produce a distinct stream of (ie_i1,...ie_ik).
3001
(TODO: can we just create a list of pointers and hope the expressions
3002
will not substitute themselves on fix_fields()? or we need to wrap
3003
them into Item_direct_view_refs and store pointers to those. The
3004
pointers to Item_direct_view_refs are guaranteed to be stable as
3005
Item_direct_view_refs doesn't substitute itself with anything in
3006
Item_direct_view_ref::fix_fields.
3008
sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
3009
sj_nest->nested_join->sj_outer_expr_list.empty();
3011
if (subq_pred->left_expr->cols() == 1)
3013
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr);
3015
Item *item_eq= new Item_func_eq(subq_pred->left_expr,
3016
subq_lex->ref_pointer_array[0]);
3017
item_eq->name= (char*)subq_sj_cond_name;
3018
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3022
for (uint32_t i= 0; i < subq_pred->left_expr->cols(); i++)
3024
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->
3027
new Item_func_eq(subq_pred->left_expr->element_index(i),
3028
subq_lex->ref_pointer_array[i]);
3029
item_eq->name= (char*)subq_sj_cond_name + (i % 64);
3030
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3033
/* Fix the created equality and AND */
3034
sj_nest->sj_on_expr->fix_fields(parent_join->session, &sj_nest->sj_on_expr);
3037
Walk through sj nest's WHERE and ON expressions and call
3038
item->fix_table_changes() for all items.
3040
sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr);
3041
fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
3044
/* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
3045
subq_lex->master_unit()->exclude_level();
3047
/* Inject sj_on_expr into the parent's WHERE or ON */
3050
emb_tbl_nest->on_expr= and_items(emb_tbl_nest->on_expr,
3051
sj_nest->sj_on_expr);
3052
emb_tbl_nest->on_expr->fix_fields(parent_join->session, &emb_tbl_nest->on_expr);
3056
/* Inject into the WHERE */
3057
parent_join->conds= and_items(parent_join->conds, sj_nest->sj_on_expr);
3058
parent_join->conds->fix_fields(parent_join->session, &parent_join->conds);
3059
parent_join->select_lex->where= parent_join->conds;
3067
Convert candidate subquery predicates to semi-joins
3070
JOIN::flatten_subqueries()
3073
Convert candidate subquery predicates to semi-joins.
3080
bool JOIN::flatten_subqueries()
3082
Item_in_subselect **in_subq;
3083
Item_in_subselect **in_subq_end;
3085
if (sj_subselects.elements() == 0)
3088
/* 1. Fix children subqueries */
3089
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
3090
in_subq != in_subq_end; in_subq++)
3092
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3093
child_join->outer_tables = child_join->tables;
3094
if (child_join->flatten_subqueries())
3096
(*in_subq)->sj_convert_priority=
3097
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
3100
bool outer_join_disable_semi_join= false;
3102
* Temporary measure: disable semi-joins when they are together with outer
3105
* @see LP Bug #314911
3107
for (TableList *tbl= select_lex->leaf_tables; tbl; tbl=tbl->next_leaf)
3109
TableList *embedding= tbl->embedding;
3110
if (tbl->on_expr || (tbl->embedding && !(embedding->sj_on_expr &&
3111
!embedding->embedding)))
3113
in_subq= sj_subselects.front();
3114
outer_join_disable_semi_join= true;
3118
if (! outer_join_disable_semi_join)
3121
2. Pick which subqueries to convert:
3122
sort the subquery array
3123
- prefer correlated subqueries over uncorrelated;
3124
- prefer subqueries that have greater number of outer tables;
3126
sj_subselects.sort(subq_sj_candidate_cmp);
3127
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
3128
/* Replace all subqueries to be flattened with Item_int(1) */
3129
for (in_subq= sj_subselects.front();
3130
in_subq != in_subq_end &&
3131
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3134
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
3138
for (in_subq= sj_subselects.front();
3139
in_subq != in_subq_end &&
3140
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3143
if (convert_subq_to_sj(this, *in_subq))
3148
/* 3. Finalize those we didn't convert */
3149
for (; in_subq!= in_subq_end; in_subq++)
3151
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3152
Item_subselect::trans_res res;
3153
(*in_subq)->changed= 0;
3154
(*in_subq)->fixed= 0;
3155
res= (*in_subq)->select_transformer(child_join);
3156
if (res == Item_subselect::RES_ERROR)
3159
(*in_subq)->changed= 1;
3160
(*in_subq)->fixed= 1;
3162
Item *substitute= (*in_subq)->substitution;
3163
bool do_fix_fields= !(*in_subq)->substitution->fixed;
3164
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
3167
//if ((*in_subq)->fix_fields(session, (*in_subq)->ref_ptr))
3170
sj_subselects.clear();
3176
Setup for execution all subqueries of a query, for which the optimizer
3177
chose hash semi-join.
3179
@details Iterate over all subqueries of the query, and if they are under an
3180
IN predicate, and the optimizer chose to compute it via hash semi-join:
3181
- try to initialize all data structures needed for the materialized execution
3182
of the IN predicate,
3183
- if this fails, then perform the IN=>EXISTS transformation which was
3184
previously blocked during JOIN::prepare.
3186
This method is part of the "code generation" query processing phase.
3188
This phase must be called after substitute_for_best_equal_field() because
3189
that function may replace items with other items from a multiple equality,
3190
and we need to reference the correct items in the index access method of the
3193
@return Operation status
3194
@retval false success.
3195
@retval true error occurred.
3198
bool JOIN::setup_subquery_materialization()
3200
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
3201
un= un->next_unit())
3203
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
3205
Item_subselect *subquery_predicate= sl->master_unit()->item;
3206
if (subquery_predicate &&
3207
subquery_predicate->substype() == Item_subselect::IN_SUBS)
3209
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
3210
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
3211
in_subs->setup_engine())
3221
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3224
find_eq_ref_candidate()
3225
table Table to be checked
3226
sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
3230
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3233
Check again if it is feasible to factor common parts with constant table
3237
true - There exists an eq_ref(outer-tables) candidate
3241
bool find_eq_ref_candidate(Table *table, table_map sj_inner_tables)
3243
KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
3248
while (1) /* For each key */
3251
KEY *keyinfo= table->key_info + key;
3252
key_part_map bound_parts= 0;
3253
if ((keyinfo->flags & HA_NOSAME) == HA_NOSAME)
3255
do /* For all equalities on all key parts */
3257
/* Check if this is "t.keypart = expr(outer_tables) */
3258
if (!(keyuse->used_tables & sj_inner_tables) &&
3259
!(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
3261
bound_parts |= 1 << keyuse->keypart;
3264
} while (keyuse->key == key && keyuse->table == table);
3266
if (bound_parts == PREV_BITS(uint, keyinfo->key_parts))
3268
if (keyuse->table != table)
3276
if (keyuse->table != table)
3279
while (keyuse->key == key);
3288
Pull tables out of semi-join nests, if possible
3291
pull_out_semijoin_tables()
3292
join The join where to do the semi-join flattening
3295
Try to pull tables out of semi-join nests.
3298
When this function is called, the join may have several semi-join nests
3299
(possibly within different semi-join nests), but it is guaranteed that
3300
one semi-join nest does not contain another.
3303
A table can be pulled out of the semi-join nest if
3304
- It is a constant table
3308
* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer
3310
* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.
3311
* Semi-join nests TableList::sj_inner_tables
3313
This operation is (and should be) performed at each PS execution since
3314
tables may become/cease to be constant across PS reexecutions.
3318
1 - Out of memory error
3321
int pull_out_semijoin_tables(JOIN *join)
3324
List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);
3326
/* Try pulling out of the each of the semi-joins */
3327
while ((sj_nest= sj_list_it++))
3329
/* Action #1: Mark the constant tables to be pulled out */
3330
table_map pulled_tables= 0;
3332
List_iterator<TableList> child_li(sj_nest->nested_join->join_list);
3334
while ((tbl= child_li++))
3338
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
3339
if (tbl->table->map & join->const_table_map)
3341
pulled_tables |= tbl->table->map;
3347
Action #2: Find which tables we can pull out based on
3348
update_ref_and_keys() data. Note that pulling one table out can allow
3349
us to pull out some other tables too.
3351
bool pulled_a_table;
3354
pulled_a_table= false;
3356
while ((tbl= child_li++))
3358
if (tbl->table && !(pulled_tables & tbl->table->map))
3360
if (find_eq_ref_candidate(tbl->table,
3361
sj_nest->nested_join->used_tables &
3364
pulled_a_table= true;
3365
pulled_tables |= tbl->table->map;
3369
} while (pulled_a_table);
3372
if ((sj_nest)->nested_join->used_tables == pulled_tables)
3374
(sj_nest)->sj_inner_tables= 0;
3375
while ((tbl= child_li++))
3378
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3383
/* Record the bitmap of inner tables, mark the inner tables */
3384
table_map inner_tables=(sj_nest)->nested_join->used_tables &
3386
(sj_nest)->sj_inner_tables= inner_tables;
3387
while ((tbl= child_li++))
3391
if (inner_tables & tbl->table->map)
3392
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
3394
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
460
3402
/*****************************************************************************
461
Create JoinTableS, make a guess about the table types,
3403
Create JOIN_TABS, make a guess about the table types,
462
3404
Approximate how many records will be used in each table
463
3405
*****************************************************************************/
464
ha_rows get_quick_record_count(Session *session, optimizer::SqlSelect *select, Table *table, const key_map *keys,ha_rows limit)
3408
static ha_rows get_quick_record_count(Session *session, SQL_SELECT *select,
3410
const key_map *keys,ha_rows limit)
467
3413
if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))
482
3428
return(HA_POS_ERROR); /* This shouldn't happend */
3432
This structure is used to collect info on potentially sargable
3433
predicates in order to check whether they become sargable after
3434
reading const tables.
3435
We form a bitmap of indexes that can be used for sargable predicates.
3436
Only such indexes are involved in range analysis.
3438
typedef struct st_sargable_param
3440
Field *field; /* field against which to check sargability */
3441
Item **arg_value; /* values of potential keys for lookups */
3442
uint32_t num_values; /* number of values in the above array */
3446
Calculate the best possible join and initialize the join structure.
3455
make_join_statistics(JOIN *join, TableList *tables, COND *conds,
3456
DYNAMIC_ARRAY *keyuse_array)
3460
uint32_t i,table_count,const_count,key;
3461
table_map found_const_table_map, all_table_map, found_ref, refs;
3462
key_map const_ref, eq_part;
3463
Table **table_vector;
3464
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
3465
KEYUSE *keyuse,*start_keyuse;
3466
table_map outer_join=0;
3467
SARGABLE_PARAM *sargables= 0;
3468
JOIN_TAB *stat_vector[MAX_TABLES+1];
3470
table_count=join->tables;
3471
stat=(JOIN_TAB*) join->session->calloc(sizeof(JOIN_TAB)*table_count);
3472
stat_ref=(JOIN_TAB**) join->session->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
3473
table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
3474
if (!stat || !stat_ref || !table_vector)
3475
return(1); // Eom /* purecov: inspected */
3477
join->best_ref=stat_vector;
3479
stat_end=stat+table_count;
3480
found_const_table_map= all_table_map=0;
3485
s++, tables= tables->next_leaf, i++)
3487
TableList *embedding= tables->embedding;
3490
s->const_keys.init();
3491
s->checked_keys.init();
3492
s->needed_reg.init();
3493
table_vector[i]=s->table=table=tables->table;
3494
table->pos_in_table_list= tables;
3495
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
3498
table->file->print_error(error, MYF(0));
3501
table->quick_keys.clear_all();
3502
table->reginfo.join_tab=s;
3503
table->reginfo.not_exists_optimize=0;
3504
memset(table->const_key_parts, 0,
3505
sizeof(key_part_map)*table->s->keys);
3506
all_table_map|= table->map;
3508
s->info=0; // For describe
3510
s->dependent= tables->dep_tables;
3511
s->key_dependent= 0;
3512
if (tables->schema_table)
3513
table->file->stats.records= 2;
3514
table->quick_condition_rows= table->file->stats.records;
3516
s->on_expr_ref= &tables->on_expr;
3517
if (*s->on_expr_ref)
3519
/* s is the only inner table of an outer join */
3520
if (!table->file->stats.records && !embedding)
3522
s->dependent= 0; // Ignore LEFT JOIN depend.
3523
set_position(join,const_count++,s,(KEYUSE*) 0);
3526
outer_join|= table->map;
3527
s->embedding_map= 0;
3528
for (;embedding; embedding= embedding->embedding)
3529
s->embedding_map|= embedding->nested_join->nj_map;
3532
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
3534
/* s belongs to a nested join, maybe to several embedded joins */
3535
s->embedding_map= 0;
3538
nested_join_st *nested_join= embedding->nested_join;
3539
s->embedding_map|=nested_join->nj_map;
3540
s->dependent|= embedding->dep_tables;
3541
embedding= embedding->embedding;
3542
outer_join|= nested_join->used_tables;
3547
if ((table->file->stats.records <= 1) &&
3549
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && !join->no_const_tables)
3551
set_position(join,const_count++,s,(KEYUSE*) 0);
3555
join->outer_join=outer_join;
3557
if (join->outer_join)
3560
Build transitive closure for relation 'to be dependent on'.
3561
This will speed up the plan search for many cases with outer joins,
3562
as well as allow us to catch illegal cross references/
3563
Warshall's algorithm is used to build the transitive closure.
3564
As we use bitmaps to represent the relation the complexity
3565
of the algorithm is O((number of tables)^2).
3567
for (i= 0, s= stat ; i < table_count ; i++, s++)
3569
for (uint32_t j= 0 ; j < table_count ; j++)
3571
table= stat[j].table;
3572
if (s->dependent & table->map)
3573
s->dependent |= table->reginfo.join_tab->dependent;
3576
s->table->maybe_null= 1;
3578
/* Catch illegal cross references for outer joins */
3579
for (i= 0, s= stat ; i < table_count ; i++, s++)
3581
if (s->dependent & s->table->map)
3583
join->tables=0; // Don't use join->table
3584
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
3587
s->key_dependent= s->dependent;
3591
if (conds || outer_join)
3592
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
3593
conds, join->cond_equal,
3594
~outer_join, join->select_lex, &sargables))
3597
/* Read tables with 0 or 1 rows (system tables) */
3598
join->const_table_map= 0;
3600
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
3607
join->const_table_map|=s->table->map;
3608
if ((tmp=join_read_const_table(s, p_pos)))
3611
return(1); // Fatal error
3614
found_const_table_map|= s->table->map;
3617
/* loop until no more const tables are found */
3621
more_const_tables_found:
3626
We only have to loop from stat_vector + const_count as
3627
set_position() will move all const_tables first in stat_vector
3630
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
3635
If equi-join condition by a key is null rejecting and after a
3636
substitution of a const table the key value happens to be null
3637
then we can state that there are no matches for this equi-join.
3639
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
3642
When performing an outer join operation if there are no matching rows
3643
for the single row of the outer table all the inner tables are to be
3644
null complemented and thus considered as constant tables.
3645
Here we apply this consideration to the case of outer join operations
3646
with a single inner table only because the case with nested tables
3647
would require a more thorough analysis.
3648
TODO. Apply single row substitution to null complemented inner tables
3649
for nested outer join operations.
3651
while (keyuse->table == table)
3653
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
3654
keyuse->val->is_null() && keyuse->null_rejecting)
3657
mark_as_null_row(table);
3658
found_const_table_map|= table->map;
3659
join->const_table_map|= table->map;
3660
set_position(join,const_count++,s,(KEYUSE*) 0);
3661
goto more_const_tables_found;
3667
if (s->dependent) // If dependent on some table
3669
// All dep. must be constants
3670
if (s->dependent & ~(found_const_table_map))
3672
if (table->file->stats.records <= 1L &&
3673
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
3674
!table->pos_in_table_list->embedding)
3678
join->const_table_map|=table->map;
3679
set_position(join,const_count++,s,(KEYUSE*) 0);
3680
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
3683
return(1); // Fatal error
3686
found_const_table_map|= table->map;
3690
/* check if table can be read by key or table only uses const refs */
3691
if ((keyuse=s->keyuse))
3694
while (keyuse->table == table)
3696
start_keyuse=keyuse;
3698
s->keys.set_bit(key); // QQ: remove this ?
3701
const_ref.clear_all();
3702
eq_part.clear_all();
3705
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
3707
if (!((~found_const_table_map) & keyuse->used_tables))
3708
const_ref.set_bit(keyuse->keypart);
3710
refs|=keyuse->used_tables;
3711
eq_part.set_bit(keyuse->keypart);
3714
} while (keyuse->table == table && keyuse->key == key);
3716
if (eq_part.is_prefix(table->key_info[key].key_parts) &&
3717
!table->pos_in_table_list->embedding)
3719
if ((table->key_info[key].flags & (HA_NOSAME))
3722
if (const_ref == eq_part)
3723
{ // Found everything for ref.
3727
join->const_table_map|=table->map;
3728
set_position(join,const_count++,s,start_keyuse);
3729
if (create_ref_for_key(join, s, start_keyuse,
3730
found_const_table_map))
3732
if ((tmp=join_read_const_table(s,
3733
join->positions+const_count-1)))
3736
return(1); // Fatal error
3739
found_const_table_map|= table->map;
3743
found_ref|= refs; // Table is const if all refs are const
3745
else if (const_ref == eq_part)
3746
s->const_keys.set_bit(key);
3751
} while (join->const_table_map & found_ref && ref_changed);
3754
Update info on indexes that can be used for search lookups as
3755
reading const tables may has added new sargable predicates.
3757
if (const_count && sargables)
3759
for( ; sargables->field ; sargables++)
3761
Field *field= sargables->field;
3762
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
3763
key_map possible_keys= field->key_start;
3764
possible_keys.intersect(field->table->keys_in_use_for_query);
3766
for (uint32_t j=0; j < sargables->num_values; j++)
3767
is_const&= sargables->arg_value[j]->const_item();
3769
join_tab[0].const_keys.merge(possible_keys);
3773
if (pull_out_semijoin_tables(join))
3776
/* Calc how many (possible) matched records in each table */
3778
for (s=stat ; s < stat_end ; s++)
3780
if (s->type == JT_SYSTEM || s->type == JT_CONST)
3782
/* Only one matching row */
3783
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
3786
/* Approximate found rows and time to read them */
3787
s->found_records=s->records=s->table->file->stats.records;
3788
s->read_time=(ha_rows) s->table->file->scan_time();
3791
Set a max range of how many seeks we can expect when using keys
3792
This is can't be to high as otherwise we are likely to use
3795
s->worst_seeks= cmin((double) s->found_records / 10,
3796
(double) s->read_time*3);
3797
if (s->worst_seeks < 2.0) // Fix for small tables
3801
Add to stat->const_keys those indexes for which all group fields or
3802
all select distinct fields participate in one index.
3804
add_group_and_distinct_keys(join, s);
3806
if (!s->const_keys.is_clear_all() &&
3807
!s->table->pos_in_table_list->embedding)
3811
select= make_select(s->table, found_const_table_map,
3812
found_const_table_map,
3813
*s->on_expr_ref ? *s->on_expr_ref : conds,
3817
records= get_quick_record_count(join->session, select, s->table,
3818
&s->const_keys, join->row_limit);
3819
s->quick=select->quick;
3820
s->needed_reg=select->needed_reg;
3822
if (records == 0 && s->table->reginfo.impossible_range)
3825
Impossible WHERE or ON expression
3826
In case of ON, we mark that the we match one empty NULL row.
3827
In case of WHERE, don't set found_const_table_map to get the
3828
caller to abort with a zero row result.
3830
join->const_table_map|= s->table->map;
3831
set_position(join,const_count++,s,(KEYUSE*) 0);
3833
if (*s->on_expr_ref)
3835
/* Generate empty row */
3836
s->info= "Impossible ON condition";
3837
found_const_table_map|= s->table->map;
3839
mark_as_null_row(s->table); // All fields are NULL
3842
if (records != HA_POS_ERROR)
3844
s->found_records=records;
3845
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
3851
join->join_tab=stat;
3852
join->map2table=stat_ref;
3853
join->table= join->all_tables=table_vector;
3854
join->const_tables=const_count;
3855
join->found_const_table_map=found_const_table_map;
3857
/* Find an optimal join order of the non-constant tables. */
3858
if (join->const_tables != join->tables)
3860
optimize_keyuse(join, keyuse_array);
3861
if (choose_plan(join, all_table_map & ~join->const_table_map))
3866
memcpy(join->best_positions, join->positions,
3867
sizeof(POSITION)*join->const_tables);
3868
join->best_read=1.0;
3870
/* Generate an execution plan from the found optimal join order. */
3871
return(join->session->killed || get_best_combination(join));
485
3875
/*****************************************************************************
486
3876
Check with keys are used and with tables references with tables
487
3877
Updates in stat:
490
3880
keyuse Pointer to possible keys
491
3881
*****************************************************************************/
3883
/// Used when finding key fields
3884
typedef struct key_field_t {
3886
Item *val; ///< May be empty if diff constant
3888
uint optimize; // KEY_OPTIMIZE_*
3891
If true, the condition this struct represents will not be satisfied
3894
bool null_rejecting;
3895
bool *cond_guard; /* See KEYUSE::cond_guard */
3896
uint32_t sj_pred_no; /* See KEYUSE::sj_pred_no */
3900
Merge new key definitions to old ones, remove those not used in both.
3902
This is called for OR between different levels.
3904
To be able to do 'ref_or_null' we merge a comparison of a column
3905
and 'column IS NULL' to one test. This is useful for sub select queries
3906
that are internally transformed to something like:.
3909
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
3912
KEY_FIELD::null_rejecting is processed as follows: @n
3913
result has null_rejecting=true if it is set for both ORed references.
3915
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
3916
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
3919
The result of this is that we're missing some 'ref' accesses.
3920
OptimizerTeam: Fix this
3924
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
3927
if (start == new_fields)
3928
return start; // Impossible or
3929
if (new_fields == end)
3930
return start; // No new fields, skip all
3932
KEY_FIELD *first_free=new_fields;
3934
/* Mark all found fields in old array */
3935
for (; new_fields != end ; new_fields++)
3937
for (KEY_FIELD *old=start ; old != first_free ; old++)
3939
if (old->field == new_fields->field)
3942
NOTE: below const_item() call really works as "!used_tables()", i.e.
3943
it can return false where it is feasible to make it return true.
3945
The cause is as follows: Some of the tables are already known to be
3946
const tables (the detection code is in make_join_statistics(),
3947
above the update_ref_and_keys() call), but we didn't propagate
3948
information about this: Table::const_table is not set to true, and
3949
Item::update_used_tables() hasn't been called for each item.
3950
The result of this is that we're missing some 'ref' accesses.
3951
TODO: OptimizerTeam: Fix this
3953
if (!new_fields->val->const_item())
3956
If the value matches, we can use the key reference.
3957
If not, we keep it until we have examined all new values
3959
if (old->val->eq(new_fields->val, old->field->binary()))
3961
old->level= and_level;
3962
old->optimize= ((old->optimize & new_fields->optimize &
3963
KEY_OPTIMIZE_EXISTS) |
3964
((old->optimize | new_fields->optimize) &
3965
KEY_OPTIMIZE_REF_OR_NULL));
3966
old->null_rejecting= (old->null_rejecting &&
3967
new_fields->null_rejecting);
3970
else if (old->eq_func && new_fields->eq_func &&
3971
old->val->eq_by_collation(new_fields->val,
3972
old->field->binary(),
3973
old->field->charset()))
3976
old->level= and_level;
3977
old->optimize= ((old->optimize & new_fields->optimize &
3978
KEY_OPTIMIZE_EXISTS) |
3979
((old->optimize | new_fields->optimize) &
3980
KEY_OPTIMIZE_REF_OR_NULL));
3981
old->null_rejecting= (old->null_rejecting &&
3982
new_fields->null_rejecting);
3984
else if (old->eq_func && new_fields->eq_func &&
3985
((old->val->const_item() && old->val->is_null()) ||
3986
new_fields->val->is_null()))
3988
/* field = expression OR field IS NULL */
3989
old->level= and_level;
3990
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
3992
Remember the NOT NULL value unless the value does not depend
3995
if (!old->val->used_tables() && old->val->is_null())
3996
old->val= new_fields->val;
3997
/* The referred expression can be NULL: */
3998
old->null_rejecting= 0;
4003
We are comparing two different const. In this case we can't
4004
use a key-lookup on this so it's better to remove the value
4005
and let the range optimzier handle it
4007
if (old == --first_free) // If last item
4009
*old= *first_free; // Remove old value
4010
old--; // Retry this value
4015
/* Remove all not used items */
4016
for (KEY_FIELD *old=start ; old != first_free ;)
4018
if (old->level != and_level)
4019
{ // Not used in all levels
4020
if (old == --first_free)
4022
*old= *first_free; // Remove old value
4032
Add a possible key to array of possible keys if it's usable as a key
4034
@param key_fields Pointer to add key, if usable
4035
@param and_level And level, to be stored in KEY_FIELD
4036
@param cond Condition predicate
4037
@param field Field used in comparision
4038
@param eq_func True if we used =, <=> or IS NULL
4039
@param value Value used for comparison with field
4040
@param usable_tables Tables which can be used for key optimization
4041
@param sargables IN/OUT Array of found sargable candidates
4044
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
4045
table, we store this to be able to do not exists optimization later.
4048
*key_fields is incremented if we stored a key in the array
4052
add_key_field(KEY_FIELD **key_fields,uint32_t and_level, Item_func *cond,
4053
Field *field, bool eq_func, Item **value, uint32_t num_values,
4054
table_map usable_tables, SARGABLE_PARAM **sargables)
4056
uint32_t exists_optimize= 0;
4057
if (!(field->flags & PART_KEY_FLAG))
4059
// Don't remove column IS NULL on a LEFT JOIN table
4060
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4061
!field->table->maybe_null || field->null_ptr)
4062
return; // Not a key. Skip it
4063
exists_optimize= KEY_OPTIMIZE_EXISTS;
4064
assert(num_values == 1);
4068
table_map used_tables=0;
4070
for (uint32_t i=0; i<num_values; i++)
4072
used_tables|=(value[i])->used_tables();
4073
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
4078
if (!(usable_tables & field->table->map))
4080
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4081
!field->table->maybe_null || field->null_ptr)
4082
return; // Can't use left join optimize
4083
exists_optimize= KEY_OPTIMIZE_EXISTS;
4087
JOIN_TAB *stat=field->table->reginfo.join_tab;
4088
key_map possible_keys=field->key_start;
4089
possible_keys.intersect(field->table->keys_in_use_for_query);
4090
stat[0].keys.merge(possible_keys); // Add possible keys
4093
Save the following cases:
4095
Field LIKE constant where constant doesn't start with a wildcard
4096
Field = field2 where field2 is in a different table
4103
stat[0].key_dependent|=used_tables;
4106
for (uint32_t i=0; i<num_values; i++)
4108
if (!(is_const&= value[i]->const_item()))
4112
stat[0].const_keys.merge(possible_keys);
4116
Save info to be able check whether this predicate can be
4117
considered as sargable for range analisis after reading const tables.
4118
We do not save info about equalities as update_const_equal_items
4119
will take care of updating info on keys from sargable equalities.
4122
(*sargables)->field= field;
4123
(*sargables)->arg_value= value;
4124
(*sargables)->num_values= num_values;
4127
We can't always use indexes when comparing a string index to a
4128
number. cmp_type() is checked to allow compare of dates to numbers.
4129
eq_func is NEVER true when num_values > 1
4134
Additional optimization: if we're processing
4135
"t.key BETWEEN c1 AND c1" then proceed as if we were processing
4137
TODO: This is a very limited fix. A more generic fix is possible.
4138
There are 2 options:
4139
A) Make equality propagation code be able to handle BETWEEN
4140
(including cases like t1.key BETWEEN t2.key AND t3.key)
4141
B) Make range optimizer to infer additional "t.key = c" equalities
4142
and use them in equality propagation process (see details in
4145
if ((cond->functype() != Item_func::BETWEEN) ||
4146
((Item_func_between*) cond)->negated ||
4147
!value[0]->eq(value[1], field->binary()))
4152
if (field->result_type() == STRING_RESULT)
4154
if ((*value)->result_type() != STRING_RESULT)
4156
if (field->cmp_type() != (*value)->result_type())
4162
We can't use indexes if the effective collation
4163
of the operation differ from the field collation.
4165
if (field->cmp_type() == STRING_RESULT &&
4166
((Field_str*)field)->charset() != cond->compare_collation())
4173
For the moment eq_func is always true. This slot is reserved for future
4174
extensions where we want to remembers other things than just eq comparisons
4177
/* Store possible eq field */
4178
(*key_fields)->field= field;
4179
(*key_fields)->eq_func= eq_func;
4180
(*key_fields)->val= *value;
4181
(*key_fields)->level= and_level;
4182
(*key_fields)->optimize= exists_optimize;
4184
If the condition has form "tbl.keypart = othertbl.field" and
4185
othertbl.field can be NULL, there will be no matches if othertbl.field
4187
We use null_rejecting in add_not_null_conds() to add
4188
'othertbl.field IS NOT NULL' to tab->select_cond.
4190
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
4191
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
4192
((*value)->type() == Item::FIELD_ITEM) &&
4193
((Item_field*)*value)->field->maybe_null());
4194
(*key_fields)->cond_guard= NULL;
4195
(*key_fields)->sj_pred_no= (cond->name >= subq_sj_cond_name &&
4196
cond->name < subq_sj_cond_name + 64)?
4197
cond->name - subq_sj_cond_name: UINT_MAX;
4202
Add possible keys to array of possible keys originated from a simple
4205
@param key_fields Pointer to add key, if usable
4206
@param and_level And level, to be stored in KEY_FIELD
4207
@param cond Condition predicate
4208
@param field Field used in comparision
4209
@param eq_func True if we used =, <=> or IS NULL
4210
@param value Value used for comparison with field
4211
Is NULL for BETWEEN and IN
4212
@param usable_tables Tables which can be used for key optimization
4213
@param sargables IN/OUT Array of found sargable candidates
4216
If field items f1 and f2 belong to the same multiple equality and
4217
a key is added for f1, the the same key is added for f2.
4220
*key_fields is incremented if we stored a key in the array
4224
add_key_equal_fields(KEY_FIELD **key_fields, uint32_t and_level,
4225
Item_func *cond, Item_field *field_item,
4226
bool eq_func, Item **val,
4227
uint32_t num_values, table_map usable_tables,
4228
SARGABLE_PARAM **sargables)
4230
Field *field= field_item->field;
4231
add_key_field(key_fields, and_level, cond, field,
4232
eq_func, val, num_values, usable_tables, sargables);
4233
Item_equal *item_equal= field_item->item_equal;
4237
Add to the set of possible key values every substitution of
4238
the field for an equal field included into item_equal
4240
Item_equal_iterator it(*item_equal);
4242
while ((item= it++))
4244
if (!field->eq(item->field))
4246
add_key_field(key_fields, and_level, cond, item->field,
4247
eq_func, val, num_values, usable_tables,
4255
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint32_t *and_level,
4256
COND *cond, table_map usable_tables,
4257
SARGABLE_PARAM **sargables)
4259
if (cond->type() == Item_func::COND_ITEM)
4261
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
4262
KEY_FIELD *org_key_fields= *key_fields;
4264
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
4268
add_key_fields(join, key_fields, and_level, item, usable_tables,
4270
for (; org_key_fields != *key_fields ; org_key_fields++)
4271
org_key_fields->level= *and_level;
4276
add_key_fields(join, key_fields, and_level, li++, usable_tables,
4281
KEY_FIELD *start_key_fields= *key_fields;
4283
add_key_fields(join, key_fields, and_level, item, usable_tables,
4285
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
4286
*key_fields,++(*and_level));
4293
Subquery optimization: Conditions that are pushed down into subqueries
4294
are wrapped into Item_func_trig_cond. We process the wrapped condition
4295
but need to set cond_guard for KEYUSE elements generated from it.
4298
if (cond->type() == Item::FUNC_ITEM &&
4299
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
4301
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
4302
if (!join->group_list && !join->order &&
4304
join->unit->item->substype() == Item_subselect::IN_SUBS &&
4305
!join->unit->is_union())
4307
KEY_FIELD *save= *key_fields;
4308
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
4310
// Indicate that this ref access candidate is for subquery lookup:
4311
for (; save != *key_fields; save++)
4312
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
4318
/* If item is of type 'field op field/constant' add it to key_fields */
4319
if (cond->type() != Item::FUNC_ITEM)
4321
Item_func *cond_func= (Item_func*) cond;
4322
switch (cond_func->select_optimize()) {
4323
case Item_func::OPTIMIZE_NONE:
4325
case Item_func::OPTIMIZE_KEY:
4329
if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
4330
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4332
values= cond_func->arguments()+1;
4333
if (cond_func->functype() == Item_func::NE_FUNC &&
4334
cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4335
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4337
assert(cond_func->functype() != Item_func::IN_FUNC ||
4338
cond_func->argument_count() != 2);
4339
add_key_equal_fields(key_fields, *and_level, cond_func,
4340
(Item_field*) (cond_func->key_item()->real_item()),
4342
cond_func->argument_count()-1,
4343
usable_tables, sargables);
4345
if (cond_func->functype() == Item_func::BETWEEN)
4347
values= cond_func->arguments();
4348
for (uint32_t i= 1 ; i < cond_func->argument_count() ; i++)
4350
Item_field *field_item;
4351
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
4353
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
4355
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
4356
add_key_equal_fields(key_fields, *and_level, cond_func,
4357
field_item, 0, values, 1, usable_tables,
4364
case Item_func::OPTIMIZE_OP:
4366
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
4367
cond_func->functype() == Item_func::EQUAL_FUNC);
4369
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4370
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4372
add_key_equal_fields(key_fields, *and_level, cond_func,
4373
(Item_field*) (cond_func->arguments()[0])->real_item(),
4375
cond_func->arguments()+1, 1, usable_tables,
4378
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4379
cond_func->functype() != Item_func::LIKE_FUNC &&
4380
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
4382
add_key_equal_fields(key_fields, *and_level, cond_func,
4383
(Item_field*) (cond_func->arguments()[1])->real_item(),
4385
cond_func->arguments(),1,usable_tables,
4390
case Item_func::OPTIMIZE_NULL:
4391
/* column_name IS [NOT] NULL */
4392
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4393
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4395
Item *tmp=new Item_null;
4396
if (unlikely(!tmp)) // Should never be true
4398
add_key_equal_fields(key_fields, *and_level, cond_func,
4399
(Item_field*) (cond_func->arguments()[0])->real_item(),
4400
cond_func->functype() == Item_func::ISNULL_FUNC,
4401
&tmp, 1, usable_tables, sargables);
4404
case Item_func::OPTIMIZE_EQUAL:
4405
Item_equal *item_equal= (Item_equal *) cond;
4406
Item *const_item= item_equal->get_const();
4407
Item_equal_iterator it(*item_equal);
4412
For each field field1 from item_equal consider the equality
4413
field1=const_item as a condition allowing an index access of the table
4414
with field1 by the keys value of field1.
4416
while ((item= it++))
4418
add_key_field(key_fields, *and_level, cond_func, item->field,
4419
true, &const_item, 1, usable_tables, sargables);
4425
Consider all pairs of different fields included into item_equal.
4426
For each of them (field1, field1) consider the equality
4427
field1=field2 as a condition allowing an index access of the table
4428
with field1 by the keys value of field2.
4430
Item_equal_iterator fi(*item_equal);
4431
while ((item= fi++))
4433
Field *field= item->field;
4434
while ((item= it++))
4436
if (!field->eq(item->field))
4438
add_key_field(key_fields, *and_level, cond_func, field,
4439
true, (Item **) &item, 1, usable_tables,
495
4451
Add all keys with uses 'field' for some keypart.
497
4453
If field->and_level != and_level then only mark key_part as const_part.
499
uint32_t max_part_bit(key_part_map bits)
4457
max_part_bit(key_part_map bits)
502
4460
for (found=0; bits & 1 ; found++,bits>>=1) ;
506
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)
4465
add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
4467
Field *field=key_field->field;
4468
Table *form= field->table;
4471
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
4473
for (uint32_t key= 0 ; key < form->sizeKeys() ; key++)
4475
if (!(form->keys_in_use_for_query.is_set(key)))
4478
uint32_t key_parts= (uint32_t) form->key_info[key].key_parts;
4479
for (uint32_t part=0 ; part < key_parts ; part++)
4481
if (field->eq(form->key_info[key].key_part[part].field))
4483
keyuse.table= field->table;
4484
keyuse.val = key_field->val;
4486
keyuse.keypart=part;
4487
keyuse.keypart_map= (key_part_map) 1 << part;
4488
keyuse.used_tables=key_field->val->used_tables();
4489
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
4490
keyuse.null_rejecting= key_field->null_rejecting;
4491
keyuse.cond_guard= key_field->cond_guard;
4492
keyuse.sj_pred_no= key_field->sj_pred_no;
4493
insert_dynamic(keyuse_array,(unsigned char*) &keyuse);
4501
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()));
4504
if (a->table->tablenr != b->table->tablenr)
4505
return (int) (a->table->tablenr - b->table->tablenr);
4506
if (a->key != b->key)
4507
return (int) (a->key - b->key);
4508
if (a->keypart != b->keypart)
4509
return (int) (a->keypart - b->keypart);
515
4510
// Place const values before other ones
516
if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -
517
test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))
4511
if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
4512
test((b->used_tables & ~OUTER_REF_TABLE_BIT))))
519
4514
/* 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)));
4515
return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
4516
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
4521
Add to KEY_FIELD array all 'ref' access candidates within nested join.
4523
This function populates KEY_FIELD array with entries generated from the
4524
ON condition of the given nested join, and does the same for nested joins
4525
contained within this nested join.
4527
@param[in] nested_join_table Nested join pseudo-table to process
4528
@param[in,out] end End of the key field array
4529
@param[in,out] and_level And-level
4530
@param[in,out] sargables Array of found sargable candidates
4534
We can add accesses to the tables that are direct children of this nested
4535
join (1), and are not inner tables w.r.t their neighbours (2).
4537
Example for #1 (outer brackets pair denotes nested join this function is
4540
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
4544
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
4546
In examples 1-2 for condition cond, we can add 'ref' access candidates to
4550
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
4552
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
4555
static void add_key_fields_for_nj(JOIN *join, TableList *nested_join_table,
4556
KEY_FIELD **end, uint32_t *and_level,
4557
SARGABLE_PARAM **sargables)
4559
List_iterator<TableList> li(nested_join_table->nested_join->join_list);
4560
List_iterator<TableList> li2(nested_join_table->nested_join->join_list);
4561
bool have_another = false;
4562
table_map tables= 0;
4564
assert(nested_join_table->nested_join);
4566
while ((table= li++) || (have_another && (li=li2, have_another=false,
4569
if (table->nested_join)
4571
if (!table->on_expr)
4573
/* It's a semi-join nest. Walk into it as if it wasn't a nest */
4576
li= List_iterator<TableList>(table->nested_join->join_list);
4579
add_key_fields_for_nj(join, table, end, and_level, sargables);
4582
if (!table->on_expr)
4583
tables |= table->table->map;
4585
if (nested_join_table->on_expr)
4586
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
781
4850
/* Intersect the keys of all group fields. */
782
4851
cur_item= indexed_fields_it++;
783
possible_keys|= cur_item->field->part_of_key;
4852
possible_keys.merge(cur_item->field->part_of_key);
784
4853
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
4855
possible_keys.intersect(cur_item->field->part_of_key);
4858
if (!possible_keys.is_clear_all())
4859
join_tab->const_keys.merge(possible_keys);
4863
/*****************************************************************************
4864
Go through all combinations of not marked tables and find the one
4865
which uses least records
4866
*****************************************************************************/
4868
/** Save const tables first as used tables. */
4871
set_position(JOIN *join,uint32_t idx,JOIN_TAB *table,KEYUSE *key)
4873
join->positions[idx].table= table;
4874
join->positions[idx].key=key;
4875
join->positions[idx].records_read=1.0; /* This is a const table */
4876
join->positions[idx].ref_depend_map= 0;
4878
/* Move the const table as down as possible in best_ref */
4879
JOIN_TAB **pos=join->best_ref+idx+1;
4880
JOIN_TAB *next=join->best_ref[idx];
4881
for (;next != table ; pos++)
4883
JOIN_TAB *tmp=pos[0];
4887
join->best_ref[idx]=table;
4892
Given a semi-join nest, find out which of the IN-equalities are bound
4895
get_bound_sj_equalities()
4896
sj_nest Semi-join nest
4897
remaining_tables Tables that are not yet bound
4900
Given a semi-join nest, find out which of the IN-equalities have their
4901
left part expression bound (i.e. the said expression doesn't refer to
4902
any of remaining_tables and can be evaluated).
4905
Bitmap of bound IN-equalities.
4908
uint64_t get_bound_sj_equalities(TableList *sj_nest,
4909
table_map remaining_tables)
4911
List_iterator<Item> li(sj_nest->nested_join->sj_outer_expr_list);
4915
while ((item= li++))
4918
Q: should this take into account equality propagation and how?
4919
A: If e->outer_side is an Item_field, walk over the equality
4920
class and see if there is an element that is bound?
4921
(this is an optional feature)
4923
if (!(item->used_tables() & remaining_tables))
4933
Find the best access path for an extension of a partial execution
4934
plan and add this path to the plan.
4936
The function finds the best access path to table 's' from the passed
4937
partial plan where an access path is the general term for any means to
4938
access the data in 's'. An access path may use either an index or a scan,
4939
whichever is cheaper. The input partial plan is passed via the array
4940
'join->positions' of length 'idx'. The chosen access method for 's' and its
4941
cost are stored in 'join->positions[idx]'.
4943
@param join pointer to the structure providing all context info
4945
@param s the table to be joined by the function
4946
@param session thread for the connection that submitted the query
4947
@param remaining_tables set of tables not included into the partial plan yet
4948
@param idx the length of the partial plan
4949
@param record_count estimate for the number of records returned by the
4951
@param read_time the cost of the partial plan
4958
best_access_path(JOIN *join,
4961
table_map remaining_tables,
4963
double record_count,
4966
KEYUSE *best_key= 0;
4967
uint32_t best_max_key_part= 0;
4968
bool found_constraint= 0;
4969
double best= DBL_MAX;
4970
double best_time= DBL_MAX;
4971
double records= DBL_MAX;
4972
table_map best_ref_depends_map= 0;
4975
uint32_t best_is_sj_inside_out= 0;
4978
{ /* Use key if possible */
4979
Table *table= s->table;
4980
KEYUSE *keyuse,*start_key=0;
4981
double best_records= DBL_MAX;
4982
uint32_t max_key_part=0;
4983
uint64_t bound_sj_equalities= 0;
4984
bool try_sj_inside_out= false;
4986
Discover the bound equalites. We need to do this, if
4987
1. The next table is an SJ-inner table, and
4988
2. It is the first table from that semijoin, and
4989
3. We're not within a semi-join range (i.e. all semi-joins either have
4990
all or none of their tables in join_table_map), except
4991
s->emb_sj_nest (which we've just entered).
4992
3. All correlation references from this sj-nest are bound
4994
if (s->emb_sj_nest && // (1)
4995
s->emb_sj_nest->sj_in_exprs < 64 &&
4996
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
4997
s->emb_sj_nest->sj_inner_tables) && // (2)
4998
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
4999
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
5001
/* This table is an InsideOut scan candidate */
5002
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
5004
try_sj_inside_out= true;
5007
/* Test how we can use keys */
5008
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
5009
for (keyuse=s->keyuse ; keyuse->table == table ;)
5011
key_part_map found_part= 0;
5012
table_map found_ref= 0;
5013
uint32_t key= keyuse->key;
5014
KEY *keyinfo= table->key_info+key;
5015
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
5016
key_part_map const_part= 0;
5017
/* The or-null keypart in ref-or-null access: */
5018
key_part_map ref_or_null_part= 0;
5020
/* Calculate how many key segments of the current key we can use */
5022
uint64_t handled_sj_equalities=0;
5023
key_part_map sj_insideout_map= 0;
5025
do /* For each keypart */
5027
uint32_t keypart= keyuse->keypart;
5028
table_map best_part_found_ref= 0;
5029
double best_prev_record_reads= DBL_MAX;
5031
do /* For each way to access the keypart */
5035
if 1. expression doesn't refer to forward tables
5036
2. we won't get two ref-or-null's
5038
if (!(remaining_tables & keyuse->used_tables) &&
5039
!(ref_or_null_part && (keyuse->optimize &
5040
KEY_OPTIMIZE_REF_OR_NULL)))
5042
found_part|= keyuse->keypart_map;
5043
if (!(keyuse->used_tables & ~join->const_table_map))
5044
const_part|= keyuse->keypart_map;
5046
double tmp2= prev_record_reads(join, idx, (found_ref |
5047
keyuse->used_tables));
5048
if (tmp2 < best_prev_record_reads)
5050
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
5051
best_prev_record_reads= tmp2;
5053
if (rec > keyuse->ref_table_rows)
5054
rec= keyuse->ref_table_rows;
5056
If there is one 'key_column IS NULL' expression, we can
5057
use this ref_or_null optimisation of this field
5059
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
5060
ref_or_null_part |= keyuse->keypart_map;
5063
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
5065
if (!(remaining_tables & keyuse->used_tables))
5066
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
5069
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
5070
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
5075
} while (keyuse->table == table && keyuse->key == key &&
5076
keyuse->keypart == keypart);
5077
found_ref|= best_part_found_ref;
5078
} while (keyuse->table == table && keyuse->key == key);
5081
Assume that that each key matches a proportional part of table.
5083
if (!found_part && !handled_sj_equalities)
5084
continue; // Nothing usable found
5086
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
5087
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
5089
bool sj_inside_out_scan= false;
5091
found_constraint= 1;
5093
Check if InsideOut scan is applicable:
5094
1. All IN-equalities are either "bound" or "handled"
5095
2. Index keyparts are
5098
if (try_sj_inside_out &&
5099
table->covering_keys.is_set(key) &&
5100
(handled_sj_equalities | bound_sj_equalities) == // (1)
5101
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
5103
uint32_t n_fixed_parts= max_part_bit(found_part);
5104
if (n_fixed_parts != keyinfo->key_parts &&
5105
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
5106
PREV_BITS(uint, keyinfo->key_parts))
5109
Not all parts are fixed. Produce bitmap of remaining bits and
5110
check if all of them are covered.
5112
sj_inside_out_scan= true;
5116
It's a confluent ref scan.
5118
That is, all found KEYUSE elements refer to IN-equalities,
5119
and there is really no ref access because there is no
5120
t.keypart0 = {bound expression}
5122
Calculate the cost of complete loose index scan.
5124
records= (double)s->table->file->stats.records;
5126
/* The cost is entire index scan cost (divided by 2) */
5127
best_time= s->table->file->index_only_read_time(key, records);
5129
/* Now figure how many different keys we will get */
5131
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
5132
records= records / rpc;
5139
Check if we found full key
5141
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
5144
max_key_part= UINT32_MAX;
5145
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
5147
tmp = prev_record_reads(join, idx, found_ref);
5153
{ /* We found a const key */
5155
ReuseRangeEstimateForRef-1:
5156
We get here if we've found a ref(const) (c_i are constants):
5157
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
5159
If range optimizer was able to construct a "range"
5160
access on this index, then its condition "quick_cond" was
5161
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
5162
from the range optimizer.
5164
Proof of (*): By properties of range and ref optimizers
5165
quick_cond will be equal or tighther than ref_const_cond.
5166
ref_const_cond already covers "smallest" possible interval -
5167
a singlepoint interval over all keyparts. Therefore,
5168
quick_cond is equivalent to ref_const_cond (if it was an
5169
empty interval we wouldn't have got here).
5171
if (table->quick_keys.is_set(key))
5172
records= (double) table->quick_rows[key];
5175
/* quick_range couldn't use key! */
5176
records= (double) s->records/rec;
5181
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
5182
{ /* Prefer longer keys */
5184
((double) s->records / (double) rec *
5186
((double) (table->s->max_key_length-keyinfo->key_length) /
5187
(double) table->s->max_key_length)));
5189
records=2.0; /* Can't be as good as a unique */
5192
ReuseRangeEstimateForRef-2: We get here if we could not reuse
5193
E(#rows) from range optimizer. Make another try:
5195
If range optimizer produced E(#rows) for a prefix of the ref
5196
access we're considering, and that E(#rows) is lower then our
5197
current estimate, make an adjustment. The criteria of when we
5198
can make an adjustment is a special case of the criteria used
5199
in ReuseRangeEstimateForRef-3.
5201
if (table->quick_keys.is_set(key) &&
5202
const_part & (1 << table->quick_key_parts[key]) &&
5203
table->quick_n_ranges[key] == 1 &&
5204
records > (double) table->quick_rows[key])
5206
records= (double) table->quick_rows[key];
5209
/* Limit the number of matched rows */
5211
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5212
if (table->covering_keys.is_set(key))
5214
/* we can use only index tree */
5215
tmp= record_count * table->file->index_only_read_time(key, tmp);
5218
tmp= record_count*cmin(tmp,s->worst_seeks);
5224
Use as much key-parts as possible and a uniq key is better
5225
than a not unique key
5226
Set tmp to (previous record count) * (records / combination)
5228
if ((found_part & 1) &&
5229
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
5230
found_part == PREV_BITS(uint,keyinfo->key_parts)))
5232
max_key_part= max_part_bit(found_part);
5234
ReuseRangeEstimateForRef-3:
5235
We're now considering a ref[or_null] access via
5236
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
5237
(same-as-above but with one cond replaced
5238
with "t.keypart_i IS NULL")] (**)
5240
Try re-using E(#rows) from "range" optimizer:
5241
We can do so if "range" optimizer used the same intervals as
5242
in (**). The intervals used by range optimizer may be not
5243
available at this point (as "range" access might have choosen to
5244
create quick select over another index), so we can't compare
5245
them to (**). We'll make indirect judgements instead.
5246
The sufficient conditions for re-use are:
5247
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
5248
this is not satisfied we have no way to know which ranges
5249
will be actually scanned by 'ref' until we execute the
5251
(C2) max #key parts in 'range' access == K == max_key_part (this
5252
is apparently a necessary requirement)
5254
We also have a property that "range optimizer produces equal or
5255
tighter set of scan intervals than ref(const) optimizer". Each
5256
of the intervals in (**) are "tightest possible" intervals when
5257
one limits itself to using keyparts 1..K (which we do in #2).
5258
From here it follows that range access used either one, or
5259
both of the (I1) and (I2) intervals:
5261
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
5262
(same-as-above but with one cond replaced
5263
with "t.keypart_i IS NULL") (I2)
5265
The remaining part is to exclude the situation where range
5266
optimizer used one interval while we're considering
5267
ref-or-null and looking for estimate for two intervals. This
5268
is done by last limitation:
5270
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
5272
if (table->quick_keys.is_set(key) && !found_ref && //(C1)
5273
table->quick_key_parts[key] == max_key_part && //(C2)
5274
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
5276
tmp= records= (double) table->quick_rows[key];
5280
/* Check if we have statistic about the distribution */
5281
if ((records= keyinfo->rec_per_key[max_key_part-1]))
5284
Fix for the case where the index statistics is too
5286
(1) We're considering ref(const) and there is quick select
5288
(2) and that quick select uses more keyparts (i.e. it will
5289
scan equal/smaller interval then this ref(const))
5290
(3) and E(#rows) for quick select is higher then our
5293
We'll use E(#rows) from quick select.
5295
Q: Why do we choose to use 'ref'? Won't quick select be
5296
cheaper in some cases ?
5297
TODO: figure this out and adjust the plan choice if needed.
5299
if (!found_ref && table->quick_keys.is_set(key) && // (1)
5300
table->quick_key_parts[key] > max_key_part && // (2)
5301
records < (double)table->quick_rows[key]) // (3)
5302
records= (double)table->quick_rows[key];
5309
Assume that the first key part matches 1% of the file
5310
and that the whole key matches 10 (duplicates) or 1
5312
Assume also that more key matches proportionally more
5314
This gives the formula:
5315
records = (x * (b-a) + a*c-b)/(c-1)
5317
b = records matched by whole key
5318
a = records matched by first key part (1% of all records?)
5319
c = number of key parts in key
5320
x = used key parts (1 <= x <= c)
5323
if (!(rec_per_key=(double)
5324
keyinfo->rec_per_key[keyinfo->key_parts-1]))
5325
rec_per_key=(double) s->records/rec+1;
5329
else if (rec_per_key/(double) s->records >= 0.01)
5333
double a=s->records*0.01;
5334
if (keyinfo->key_parts > 1)
5335
tmp= (max_key_part * (rec_per_key - a) +
5336
a*keyinfo->key_parts - rec_per_key)/
5337
(keyinfo->key_parts-1);
5340
set_if_bigger(tmp,1.0);
5342
records = (uint32_t) tmp;
5345
if (ref_or_null_part)
5347
/* We need to do two key searches to find key */
5353
ReuseRangeEstimateForRef-4: We get here if we could not reuse
5354
E(#rows) from range optimizer. Make another try:
5356
If range optimizer produced E(#rows) for a prefix of the ref
5357
access we're considering, and that E(#rows) is lower then our
5358
current estimate, make the adjustment.
5360
The decision whether we can re-use the estimate from the range
5361
optimizer is the same as in ReuseRangeEstimateForRef-3,
5362
applied to first table->quick_key_parts[key] key parts.
5364
if (table->quick_keys.is_set(key) &&
5365
table->quick_key_parts[key] <= max_key_part &&
5366
const_part & (1 << table->quick_key_parts[key]) &&
5367
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
5368
const_part) ? 1 : 0) &&
5369
records > (double) table->quick_rows[key])
5371
tmp= records= (double) table->quick_rows[key];
5375
/* Limit the number of matched rows */
5376
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5377
if (table->covering_keys.is_set(key))
5379
/* we can use only index tree */
5380
tmp= record_count * table->file->index_only_read_time(key, tmp);
5383
tmp= record_count * cmin(tmp,s->worst_seeks);
5386
tmp= best_time; // Do nothing
5389
if (sj_inside_out_scan && !start_key)
5397
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
5399
best_time= tmp + records/(double) TIME_FOR_COMPARE;
5401
best_records= records;
5402
best_key= start_key;
5403
best_max_key_part= max_key_part;
5404
best_ref_depends_map= found_ref;
5405
best_is_sj_inside_out= sj_inside_out_scan;
5408
records= best_records;
5412
Don't test table scan if it can't be better.
5413
Prefer key lookup if we would use the same key for scanning.
5415
Don't do a table scan on InnoDB tables, if we can read the used
5416
parts of the row from any of the used index.
5417
This is because table scans uses index and we would not win
5418
anything by using a table scan.
5420
A word for word translation of the below if-statement in sergefp's
5421
understanding: we check if we should use table scan if:
5422
(1) The found 'ref' access produces more records than a table scan
5423
(or index scan, or quick select), or 'ref' is more expensive than
5425
(2) This doesn't hold: the best way to perform table scan is to to perform
5426
'range' access using index IDX, and the best way to perform 'ref'
5427
access is to use the same index IDX, with the same or more key parts.
5428
(note: it is not clear how this rule is/should be extended to
5429
index_merge quick selects)
5430
(3) See above note about InnoDB.
5431
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
5432
path, but there is no quick select)
5433
If the condition in the above brackets holds, then the only possible
5434
"table scan" access method is ALL/index (there is no quick select).
5435
Since we have a 'ref' access path, and FORCE INDEX instructs us to
5436
choose it over ALL/index, there is no need to consider a full table
5439
if ((records >= s->found_records || best > s->read_time) && // (1)
5440
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
5441
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
5442
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
5443
! s->table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
5444
!(s->table->force_index && best_key && !s->quick)) // (4)
5445
{ // Check full join
5446
ha_rows rnd_records= s->found_records;
5448
If there is a filtering condition on the table (i.e. ref analyzer found
5449
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
5450
preceding this table in the join order we're now considering), then
5451
assume that 25% of the rows will be filtered out by this condition.
5453
This heuristic is supposed to force tables used in exprZ to be before
5454
this table in join order.
5456
if (found_constraint)
5457
rnd_records-= rnd_records/4;
5460
If applicable, get a more accurate estimate. Don't use the two
5463
if (s->table->quick_condition_rows != s->found_records)
5464
rnd_records= s->table->quick_condition_rows;
5467
Range optimizer never proposes a RANGE if it isn't better
5468
than FULL: so if RANGE is present, it's always preferred to FULL.
5469
Here we estimate its cost.
5475
- read record range through 'quick'
5476
- skip rows which does not satisfy WHERE constraints
5478
We take into account possible use of join cache for ALL/index
5479
access (see first else-branch below), but we don't take it into
5480
account here for range/index_merge access. Find out why this is so.
5483
(s->quick->read_time +
5484
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
5488
/* Estimate cost of reading table. */
5489
tmp= s->table->file->scan_time();
5490
if (s->table->map & join->outer_join) // Can't use join cache
5493
For each record we have to:
5494
- read the whole table record
5495
- skip rows which does not satisfy join condition
5499
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
5503
/* We read the table as many times as join buffer becomes full. */
5504
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
5506
(double) session->variables.join_buff_size));
5508
We don't make full cartesian product between rows in the scanned
5509
table and existing records because we skip all rows from the
5510
scanned table, which does not satisfy join condition when
5511
we read the table (see flush_cached_records for details). Here we
5512
take into account cost to read and skip these records.
5514
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
5519
We estimate the cost of evaluating WHERE clause for found records
5520
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
5521
tmp give us total cost of using Table SCAN
5523
if (best == DBL_MAX ||
5524
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
5525
best + record_count/(double) TIME_FOR_COMPARE*records))
5528
If the table has a range (s->quick is set) make_join_select()
5529
will ensure that this will be used
5532
records= rows2double(rnd_records);
5534
/* range/index_merge/ALL/index access method are "independent", so: */
5535
best_ref_depends_map= 0;
5536
best_is_sj_inside_out= false;
5540
/* Update the cost information for the current partial plan */
5541
join->positions[idx].records_read= records;
5542
join->positions[idx].read_time= best;
5543
join->positions[idx].key= best_key;
5544
join->positions[idx].table= s;
5545
join->positions[idx].ref_depend_map= best_ref_depends_map;
5546
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
5549
idx == join->const_tables &&
5550
s->table == join->sort_by_table &&
5551
join->unit->select_limit_cnt >= records)
5552
join->sort_by_table= (Table*) 1; // Must use temporary table
5559
Selects and invokes a search strategy for an optimal query plan.
5561
The function checks user-configurable parameters that control the search
5562
strategy for an optimal plan, selects the search method and then invokes
5563
it. Each specific optimization procedure stores the final optimal plan in
5564
the array 'join->best_positions', and the cost of the plan in
5567
@param join pointer to the structure providing all context info for
5569
@param join_tables set of the tables in the query
5572
'MAX_TABLES+2' denotes the old implementation of find_best before
5573
the greedy version. Will be removed when greedy_search is approved.
5582
choose_plan(JOIN *join, table_map join_tables)
5584
uint32_t search_depth= join->session->variables.optimizer_search_depth;
5585
uint32_t prune_level= join->session->variables.optimizer_prune_level;
5586
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
5588
join->cur_embedding_map= 0;
5589
reset_nj_counters(join->join_list);
5591
if (SELECT_STRAIGHT_JOIN option is set)
5592
reorder tables so dependent tables come after tables they depend
5593
on, otherwise keep tables in the order they were specified in the query
5595
Apply heuristic: pre-sort all access plans with respect to the number of
5598
my_qsort(join->best_ref + join->const_tables,
5599
join->tables - join->const_tables, sizeof(JOIN_TAB*),
5600
straight_join ? join_tab_cmp_straight : join_tab_cmp);
5601
join->cur_emb_sj_nests= 0;
5604
optimize_straight_join(join, join_tables);
5608
if (search_depth == MAX_TABLES+2)
5610
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
5611
the greedy version. Will be removed when greedy_search is approved.
5613
join->best_read= DBL_MAX;
5614
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
5619
if (search_depth == 0)
5620
/* Automatically determine a reasonable value for 'search_depth' */
5621
search_depth= determine_search_depth(join);
5622
if (greedy_search(join, join_tables, search_depth, prune_level))
5628
Store the cost of this query into a user variable
5629
Don't update last_query_cost for statements that are not "flat joins" :
5630
i.e. they have subqueries, unions or call stored procedures.
5631
TODO: calculate a correct cost for a query with subqueries and UNIONs.
5633
if (join->session->lex->is_single_level_stmt())
5634
join->session->status_var.last_query_cost= join->best_read;
5640
Compare two JOIN_TAB objects based on the number of accessed records.
5642
@param ptr1 pointer to first JOIN_TAB object
5643
@param ptr2 pointer to second JOIN_TAB object
800
5646
The order relation implemented by join_tab_cmp() is not transitive,
5698
Heuristic procedure to automatically guess a reasonable degree of
5699
exhaustiveness for the greedy search procedure.
5701
The procedure estimates the optimization time and selects a search depth
5702
big enough to result in a near-optimal QEP, that doesn't take too long to
5703
find. If the number of tables in the query exceeds some constant, then
5704
search_depth is set to this constant.
5706
@param join pointer to the structure providing all context info for
5710
This is an extremely simplistic implementation that serves as a stub for a
5711
more advanced analysis of the join. Ideally the search depth should be
5712
determined by learning from previous query optimizations, because it will
5713
depend on the CPU power (and other factors).
5716
this value should be determined dynamically, based on statistics:
5717
uint32_t max_tables_for_exhaustive_opt= 7;
5720
this value could be determined by some mapping of the form:
5721
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5724
A positive integer that specifies the search depth (and thus the
5725
exhaustiveness) of the depth-first search algorithm used by
5730
determine_search_depth(JOIN *join)
5732
uint32_t table_count= join->tables - join->const_tables;
5733
uint32_t search_depth;
5734
/* TODO: this value should be determined dynamically, based on statistics: */
5735
uint32_t max_tables_for_exhaustive_opt= 7;
5737
if (table_count <= max_tables_for_exhaustive_opt)
5738
search_depth= table_count+1; // use exhaustive for small number of tables
5741
TODO: this value could be determined by some mapping of the form:
5742
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5744
search_depth= max_tables_for_exhaustive_opt; // use greedy search
5746
return search_depth;
5751
Select the best ways to access the tables in a query without reordering them.
5753
Find the best access paths for each query table and compute their costs
5754
according to their order in the array 'join->best_ref' (thus without
5755
reordering the join tables). The function calls sequentially
5756
'best_access_path' for each table in the query to select the best table
5757
access method. The final optimal plan is stored in the array
5758
'join->best_positions', and the corresponding cost in 'join->best_read'.
5760
@param join pointer to the structure providing all context info for
5762
@param join_tables set of the tables in the query
5765
This function can be applied to:
5766
- queries with STRAIGHT_JOIN
5767
- internally to compute the cost of an arbitrary QEP
5769
Thus 'optimize_straight_join' can be used at any stage of the query
5770
optimization process to finalize a QEP as it is.
5774
optimize_straight_join(JOIN *join, table_map join_tables)
5777
uint32_t idx= join->const_tables;
5778
double record_count= 1.0;
5779
double read_time= 0.0;
5781
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
5783
/* Find the best access method from 's' to the current partial plan */
5784
advance_sj_state(join_tables, s);
5785
best_access_path(join, s, join->session, join_tables, idx,
5786
record_count, read_time);
5787
/* compute the cost of the new plan extended with 's' */
5788
record_count*= join->positions[idx].records_read;
5789
read_time+= join->positions[idx].read_time;
5790
join_tables&= ~(s->table->map);
5794
read_time+= record_count / (double) TIME_FOR_COMPARE;
5795
if (join->sort_by_table &&
5796
join->sort_by_table != join->positions[join->const_tables].table->table)
5797
read_time+= record_count; // We have to make a temp table
5798
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
5799
join->best_read= read_time;
5804
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
5806
The search procedure uses a hybrid greedy/exhaustive search with controlled
5807
exhaustiveness. The search is performed in N = card(remaining_tables)
5808
steps. Each step evaluates how promising is each of the unoptimized tables,
5809
selects the most promising table, and extends the current partial QEP with
5810
that table. Currenly the most 'promising' table is the one with least
5811
expensive extension.\
5813
There are two extreme cases:
5814
-# When (card(remaining_tables) < search_depth), the estimate finds the
5815
best complete continuation of the partial QEP. This continuation can be
5816
used directly as a result of the search.
5817
-# When (search_depth == 1) the 'best_extension_by_limited_search'
5818
consideres the extension of the current QEP with each of the remaining
5821
All other cases are in-between these two extremes. Thus the parameter
5822
'search_depth' controlls the exhaustiveness of the search. The higher the
5823
value, the longer the optimizaton time and possibly the better the
5824
resulting plan. The lower the value, the fewer alternative plans are
5825
estimated, but the more likely to get a bad QEP.
5827
All intermediate and final results of the procedure are stored in 'join':
5828
- join->positions : modified for every partial QEP that is explored
5829
- join->best_positions: modified for the current best complete QEP
5830
- join->best_read : modified for the current best complete QEP
5831
- join->best_ref : might be partially reordered
5833
The final optimal plan is stored in 'join->best_positions', and its
5834
corresponding cost in 'join->best_read'.
5837
The following pseudocode describes the algorithm of 'greedy_search':
5840
procedure greedy_search
5841
input: remaining_tables
5846
(t, a) = best_extension(pplan, remaining_tables);
5847
pplan = concat(pplan, (t, a));
5848
remaining_tables = remaining_tables - t;
5849
} while (remaining_tables != {})
5854
where 'best_extension' is a placeholder for a procedure that selects the
5855
most "promising" of all tables in 'remaining_tables'.
5856
Currently this estimate is performed by calling
5857
'best_extension_by_limited_search' to evaluate all extensions of the
5858
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
5859
mainly depends on that of 'best_extension_by_limited_search'.
5862
If 'best_extension()' == 'best_extension_by_limited_search()', then the
5863
worst-case complexity of this algorithm is <=
5864
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
5865
complexity of greedy_search is O(N!).
5868
In the future, 'greedy_search' might be extended to support other
5869
implementations of 'best_extension', e.g. some simpler quadratic procedure.
5871
@param join pointer to the structure providing all context info
5873
@param remaining_tables set of tables not included into the partial plan yet
5874
@param search_depth controlls the exhaustiveness of the search
5875
@param prune_level the pruning heuristics that should be applied during
5885
greedy_search(JOIN *join,
5886
table_map remaining_tables,
5887
uint32_t search_depth,
5888
uint32_t prune_level)
5890
double record_count= 1.0;
5891
double read_time= 0.0;
5892
uint32_t idx= join->const_tables; // index into 'join->best_ref'
5894
uint32_t size_remain; // cardinality of remaining_tables
5896
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
5898
/* number of tables that remain to be optimized */
5899
size_remain= my_count_bits(remaining_tables);
5902
/* Find the extension of the current QEP with the lowest cost */
5903
join->best_read= DBL_MAX;
5904
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
5905
read_time, search_depth, prune_level))
5908
if (size_remain <= search_depth)
5911
'join->best_positions' contains a complete optimal extension of the
5912
current partial QEP.
5917
/* select the first table in the optimal extension as most promising */
5918
best_pos= join->best_positions[idx];
5919
best_table= best_pos.table;
5921
Each subsequent loop of 'best_extension_by_limited_search' uses
5922
'join->positions' for cost estimates, therefore we have to update its
5925
join->positions[idx]= best_pos;
5927
/* find the position of 'best_table' in 'join->best_ref' */
5929
JOIN_TAB *pos= join->best_ref[best_idx];
5930
while (pos && best_table != pos)
5931
pos= join->best_ref[++best_idx];
5932
assert((pos != NULL)); // should always find 'best_table'
5933
/* move 'best_table' at the first free position in the array of joins */
5934
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
5936
/* compute the cost of the new plan extended with 'best_table' */
5937
record_count*= join->positions[idx].records_read;
5938
read_time+= join->positions[idx].read_time;
5940
remaining_tables&= ~(best_table->table->map);
5948
Find a good, possibly optimal, query execution plan (QEP) by a possibly
5951
The procedure searches for the optimal ordering of the query tables in set
5952
'remaining_tables' of size N, and the corresponding optimal access paths to
5953
each table. The choice of a table order and an access path for each table
5954
constitutes a query execution plan (QEP) that fully specifies how to
5957
The maximal size of the found plan is controlled by the parameter
5958
'search_depth'. When search_depth == N, the resulting plan is complete and
5959
can be used directly as a QEP. If search_depth < N, the found plan consists
5960
of only some of the query tables. Such "partial" optimal plans are useful
5961
only as input to query optimization procedures, and cannot be used directly
5964
The algorithm begins with an empty partial plan stored in 'join->positions'
5965
and a set of N tables - 'remaining_tables'. Each step of the algorithm
5966
evaluates the cost of the partial plan extended by all access plans for
5967
each of the relations in 'remaining_tables', expands the current partial
5968
plan with the access plan that results in lowest cost of the expanded
5969
partial plan, and removes the corresponding relation from
5970
'remaining_tables'. The algorithm continues until it either constructs a
5971
complete optimal plan, or constructs an optimal plartial plan with size =
5974
The final optimal plan is stored in 'join->best_positions'. The
5975
corresponding cost of the optimal plan is in 'join->best_read'.
5978
The procedure uses a recursive depth-first search where the depth of the
5979
recursion (and thus the exhaustiveness of the search) is controlled by the
5980
parameter 'search_depth'.
5983
The pseudocode below describes the algorithm of
5984
'best_extension_by_limited_search'. The worst-case complexity of this
5985
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
5986
the complexity of greedy_search is O(N!).
5989
procedure best_extension_by_limited_search(
5990
pplan in, // in, partial plan of tables-joined-so-far
5991
pplan_cost, // in, cost of pplan
5992
remaining_tables, // in, set of tables not referenced in pplan
5993
best_plan_so_far, // in/out, best plan found so far
5994
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5995
search_depth) // in, maximum size of the plans being considered
5997
for each table T from remaining_tables
5999
// Calculate the cost of using table T as above
6000
cost = complex-series-of-calculations;
6002
// Add the cost to the cost so far.
6005
if (pplan_cost >= best_plan_so_far_cost)
6006
// pplan_cost already too great, stop search
6009
pplan= expand pplan by best_access_method;
6010
remaining_tables= remaining_tables - table T;
6011
if (remaining_tables is not an empty set
6015
best_extension_by_limited_search(pplan, pplan_cost,
6018
best_plan_so_far_cost,
6023
best_plan_so_far_cost= pplan_cost;
6024
best_plan_so_far= pplan;
6031
When 'best_extension_by_limited_search' is called for the first time,
6032
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
6033
The actual implementation provides a way to optionally use pruning
6034
heuristic (controlled by the parameter 'prune_level') to reduce the search
6035
space by skipping some partial plans.
6038
The parameter 'search_depth' provides control over the recursion
6039
depth, and thus the size of the resulting optimal plan.
6041
@param join pointer to the structure providing all context info
6043
@param remaining_tables set of tables not included into the partial plan yet
6044
@param idx length of the partial QEP in 'join->positions';
6045
since a depth-first search is used, also corresponds
6046
to the current depth of the search tree;
6047
also an index in the array 'join->best_ref';
6048
@param record_count estimate for the number of records returned by the
6050
@param read_time the cost of the best partial plan
6051
@param search_depth maximum depth of the recursion and thus size of the
6053
(0 < search_depth <= join->tables+1).
6054
@param prune_level pruning heuristics that should be applied during
6056
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
6065
best_extension_by_limited_search(JOIN *join,
6066
table_map remaining_tables,
6068
double record_count,
6070
uint32_t search_depth,
6071
uint32_t prune_level)
6073
Session *session= join->session;
6074
if (session->killed) // Abort
6078
'join' is a partial plan with lower cost than the best plan so far,
6079
so continue expanding it further with the tables in 'remaining_tables'.
6082
double best_record_count= DBL_MAX;
6083
double best_read_time= DBL_MAX;
6085
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
6087
table_map real_table_bit= s->table->map;
6088
if ((remaining_tables & real_table_bit) &&
6089
!(remaining_tables & s->dependent) &&
6090
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6092
double current_record_count, current_read_time;
6093
advance_sj_state(remaining_tables, s);
6096
psergey-insideout-todo:
6097
when best_access_path() detects it could do an InsideOut scan or
6098
some other scan, have it return an insideout scan and a flag that
6099
requests to "fork" this loop iteration. (Q: how does that behave
6100
when the depth is insufficient??)
6102
/* Find the best access method from 's' to the current partial plan */
6103
best_access_path(join, s, session, remaining_tables, idx,
6104
record_count, read_time);
6105
/* Compute the cost of extending the plan with 's' */
6106
current_record_count= record_count * join->positions[idx].records_read;
6107
current_read_time= read_time + join->positions[idx].read_time;
6109
/* Expand only partial plans with lower cost than the best QEP so far */
6110
if ((current_read_time +
6111
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
6113
restore_prev_nj_state(s);
6114
restore_prev_sj_state(remaining_tables, s);
6119
Prune some less promising partial plans. This heuristic may miss
6120
the optimal QEPs, thus it results in a non-exhaustive search.
6122
if (prune_level == 1)
6124
if (best_record_count > current_record_count ||
6125
best_read_time > current_read_time ||
6126
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
6128
if (best_record_count >= current_record_count &&
6129
best_read_time >= current_read_time &&
6130
/* TODO: What is the reasoning behind this condition? */
6131
(!(s->key_dependent & remaining_tables) ||
6132
join->positions[idx].records_read < 2.0))
6134
best_record_count= current_record_count;
6135
best_read_time= current_read_time;
6140
restore_prev_nj_state(s);
6141
restore_prev_sj_state(remaining_tables, s);
6146
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
6147
{ /* Recursively expand the current partial plan */
6148
std::swap(join->best_ref[idx], *pos);
6149
if (best_extension_by_limited_search(join,
6150
remaining_tables & ~real_table_bit,
6152
current_record_count,
6157
std::swap(join->best_ref[idx], *pos);
6161
'join' is either the best partial QEP with 'search_depth' relations,
6162
or the best complete QEP so far, whichever is smaller.
6164
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
6165
if (join->sort_by_table &&
6166
join->sort_by_table !=
6167
join->positions[join->const_tables].table->table)
6168
/* We have to make a temp table */
6169
current_read_time+= current_record_count;
6170
if ((search_depth == 1) || (current_read_time < join->best_read))
6172
memcpy(join->best_positions, join->positions,
6173
sizeof(POSITION) * (idx + 1));
6174
join->best_read= current_read_time - 0.001;
6177
restore_prev_nj_state(s);
6178
restore_prev_sj_state(remaining_tables, s);
6187
- TODO: this function is here only temporarily until 'greedy_search' is
6188
tested and accepted.
6195
find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count,
6198
Session *session= join->session;
6199
if (session->killed)
6203
read_time+=record_count/(double) TIME_FOR_COMPARE;
6204
if (join->sort_by_table &&
6205
join->sort_by_table !=
6206
join->positions[join->const_tables].table->table)
6207
read_time+=record_count; // We have to make a temp table
6208
if (read_time < join->best_read)
6210
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
6211
join->best_read= read_time - 0.001;
6215
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
6216
return(false); /* Found better before */
6219
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
6220
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
6222
table_map real_table_bit=s->table->map;
6223
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
6224
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6226
double records, best;
6227
advance_sj_state(rest_tables, s);
6228
best_access_path(join, s, session, rest_tables, idx, record_count,
6230
records= join->positions[idx].records_read;
6231
best= join->positions[idx].read_time;
6233
Go to the next level only if there hasn't been a better key on
6234
this level! This will cut down the search for a lot simple cases!
6236
double current_record_count=record_count*records;
6237
double current_read_time=read_time+best;
6238
if (best_record_count > current_record_count ||
6239
best_read_time > current_read_time ||
6240
(idx == join->const_tables && s->table == join->sort_by_table))
6242
if (best_record_count >= current_record_count &&
6243
best_read_time >= current_read_time &&
6244
(!(s->key_dependent & rest_tables) || records < 2.0))
6246
best_record_count=current_record_count;
6247
best_read_time=current_read_time;
6249
std::swap(join->best_ref[idx], *pos);
6250
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
6251
current_record_count,current_read_time))
6253
std::swap(join->best_ref[idx], *pos);
6255
restore_prev_nj_state(s);
6256
restore_prev_sj_state(rest_tables, s);
6257
if (join->select_options & SELECT_STRAIGHT_JOIN)
6258
break; // Don't test all combinations
849
6266
Find how much space the prevous read not const tables takes in cache.
851
void calc_used_field_length(Session *, JoinTable *join_tab)
6269
static void calc_used_field_length(Session *, JOIN_TAB *join_tab)
853
6271
uint32_t null_fields,blobs,fields,rec_length;
854
6272
Field **f_ptr,*field;
6273
MY_BITMAP *read_set= join_tab->table->read_set;;
856
6275
null_fields= blobs= fields= rec_length=0;
857
for (f_ptr=join_tab->table->getFields() ; (field= *f_ptr) ; f_ptr++)
6276
for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++)
859
if (field->isReadSet())
6278
if (bitmap_is_set(read_set, field->field_index))
861
6280
uint32_t flags=field->flags;
863
6282
rec_length+=field->pack_length();
864
6283
if (flags & BLOB_FLAG)
866
6285
if (!(flags & NOT_NULL_FLAG))
870
6289
if (null_fields)
873
6292
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
6295
uint32_t blob_length=(uint32_t) (join_tab->table->file->stats.mean_rec_length-
6296
(join_tab->table->getRecordLength()- rec_length));
6297
rec_length+=(uint32_t) cmax((uint32_t)4,blob_length);
6299
join_tab->used_fields=fields;
6300
join_tab->used_fieldlength=rec_length;
6301
join_tab->used_blobs=blobs;
6306
cache_record_length(JOIN *join,uint32_t idx)
6309
JOIN_TAB **pos,**end;
6310
Session *session=join->session;
6312
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
6316
JOIN_TAB *join_tab= *pos;
6317
if (!join_tab->used_fieldlength) /* Not calced yet */
6318
calc_used_field_length(session, join_tab);
6319
length+=join_tab->used_fieldlength;
6326
Get the number of different row combinations for subset of partial join
6330
join The join structure
6331
idx Number of tables in the partial join order (i.e. the
6332
partial join order is in join->positions[0..idx-1])
6333
found_ref Bitmap of tables for which we need to find # of distinct
6337
Given a partial join order (in join->positions[0..idx-1]) and a subset of
6338
tables within that join order (specified in found_ref), find out how many
6339
distinct row combinations of subset tables will be in the result of the
6342
This is used as follows: Suppose we have a table accessed with a ref-based
6343
method. The ref access depends on current rows of tables in found_ref.
6344
We want to count # of different ref accesses. We assume two ref accesses
6345
will be different if at least one of access parameters is different.
6346
Example: consider a query
6348
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
6351
t1, ref access on t1.key=c1
6352
t2, ref access on t2.key=c2
6353
t3, ref access on t3.key=t1.field
6355
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
6356
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
6357
For t3: n_ref_scans = records_read(t1)*records_read(t2)
6358
n_distinct_ref_scans = #records_read(t1)
6360
The reason for having this function (at least the latest version of it)
6361
is that we need to account for buffering in join execution.
6363
An edge-case example: if we have a non-first table in join accessed via
6364
ref(const) or ref(param) where there is a small number of different
6365
values of param, then the access will likely hit the disk cache and will
6366
not require any disk seeks.
6368
The proper solution would be to assume an LRU disk cache of some size,
6369
calculate probability of cache hits, etc. For now we just count
6370
identical ref accesses as one.
6373
Expected number of row combinations
6377
prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
6380
POSITION *pos_end= join->positions - 1;
6381
for (POSITION *pos= join->positions + idx - 1; pos != pos_end; pos--)
6383
if (pos->table->table->map & found_ref)
6385
found_ref|= pos->ref_depend_map;
6387
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
6388
with no matching row we will get position[t2].records_read==0.
6389
Actually the size of output is one null-complemented row, therefore
6390
we will use value of 1 whenever we get records_read==0.
6393
- the above case can't occur if inner part of outer join has more
6394
than one table: table with no matches will not be marked as const.
6396
- Ideally we should add 1 to records_read for every possible null-
6397
complemented row. We're not doing it because: 1. it will require
6398
non-trivial code and add overhead. 2. The value of records_read
6399
is an inprecise estimate and adding 1 (or, in the worst case,
6400
#max_nested_outer_joins=64-1) will not make it any more precise.
6402
if (pos->records_read > DBL_EPSILON)
6403
found*= pos->records_read;
6411
Set up join struct according to best position.
6415
get_best_combination(JOIN *join)
6418
table_map used_tables;
6419
JOIN_TAB *join_tab,*j;
6421
uint32_t table_count;
6422
Session *session=join->session;
6424
table_count=join->tables;
6425
if (!(join->join_tab=join_tab=
6426
(JOIN_TAB*) session->alloc(sizeof(JOIN_TAB)*table_count)))
6431
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
6432
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
6435
*j= *join->best_positions[tablenr].table;
6436
form=join->table[tablenr]=j->table;
6437
used_tables|= form->map;
6438
form->reginfo.join_tab=j;
6439
if (!*j->on_expr_ref)
6440
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
6441
if (j->type == JT_CONST)
6442
continue; // Handled in make_join_stat..
6447
if (j->type == JT_SYSTEM)
6449
if (j->keys.is_clear_all() || !(keyuse= join->best_positions[tablenr].key))
6452
if (tablenr != join->const_tables)
6455
else if (create_ref_for_key(join, j, keyuse, used_tables))
6456
return(true); // Something went wrong
6459
for (i=0 ; i < table_count ; i++)
6460
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
6461
update_depend_map(join);
6466
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
6467
table_map used_tables)
6469
KEYUSE *keyuse=org_keyuse;
6470
Session *session= join->session;
6471
uint32_t keyparts,length,key;
6475
/* Use best key from find_best */
6478
keyinfo=table->key_info+key;
6482
uint32_t found_part_ref_or_null= 0;
6484
Calculate length for the used key
6485
Stop if there is a missing key part or when we find second key_part
6486
with KEY_OPTIMIZE_REF_OR_NULL
6490
if (!(~used_tables & keyuse->used_tables))
6492
if (keyparts == keyuse->keypart &&
6493
!(found_part_ref_or_null & keyuse->optimize))
6496
length+= keyinfo->key_part[keyuse->keypart].store_length;
6497
found_part_ref_or_null|= keyuse->optimize;
6501
} while (keyuse->table == table && keyuse->key == key);
6504
/* set up fieldref */
6505
keyinfo=table->key_info+key;
6506
j->ref.key_parts=keyparts;
6507
j->ref.key_length=length;
6508
j->ref.key=(int) key;
6509
if (!(j->ref.key_buff= (unsigned char*) session->calloc(ALIGN_SIZE(length)*2)) ||
6510
!(j->ref.key_copy= (store_key**) session->alloc((sizeof(store_key*) *
6512
!(j->ref.items= (Item**) session->alloc(sizeof(Item*)*keyparts)) ||
6513
!(j->ref.cond_guards= (bool**) session->alloc(sizeof(uint*)*keyparts)))
6517
j->ref.key_buff2=j->ref.key_buff+ALIGN_SIZE(length);
6519
j->ref.null_rejecting= 0;
6520
j->ref.disable_cache= false;
6523
store_key **ref_key= j->ref.key_copy;
6524
unsigned char *key_buff=j->ref.key_buff, *null_ref_key= 0;
6525
bool keyuse_uses_no_tables= true;
6528
for (i=0 ; i < keyparts ; keyuse++,i++)
6530
while (keyuse->keypart != i ||
6531
((~used_tables) & keyuse->used_tables))
6532
keyuse++; /* Skip other parts */
6534
uint32_t maybe_null= test(keyinfo->key_part[i].null_bit);
6535
j->ref.items[i]=keyuse->val; // Save for cond removal
6536
j->ref.cond_guards[i]= keyuse->cond_guard;
6537
if (keyuse->null_rejecting)
6538
j->ref.null_rejecting |= 1 << i;
6539
keyuse_uses_no_tables= keyuse_uses_no_tables && !keyuse->used_tables;
6540
if (!keyuse->used_tables &&
6541
!(join->select_options & SELECT_DESCRIBE))
6542
{ // Compare against constant
6543
store_key_item tmp(session, keyinfo->key_part[i].field,
6544
key_buff + maybe_null,
6545
maybe_null ? key_buff : 0,
6546
keyinfo->key_part[i].length, keyuse->val);
6547
if (session->is_fatal_error)
6552
*ref_key++= get_store_key(session,
6553
keyuse,join->const_table_map,
6554
&keyinfo->key_part[i],
6555
key_buff, maybe_null);
6557
Remember if we are going to use REF_OR_NULL
6558
But only if field _really_ can be null i.e. we force JT_REF
6559
instead of JT_REF_OR_NULL in case if field can't be null
6561
if ((keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL) && maybe_null)
6562
null_ref_key= key_buff;
6563
key_buff+=keyinfo->key_part[i].store_length;
6566
*ref_key=0; // end_marker
6567
if (j->type == JT_CONST)
6568
j->table->const_table= 1;
6569
else if (((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) != HA_NOSAME) ||
6570
keyparts != keyinfo->key_parts || null_ref_key)
6572
/* Must read with repeat */
6573
j->type= null_ref_key ? JT_REF_OR_NULL : JT_REF;
6574
j->ref.null_ref_key= null_ref_key;
6576
else if (keyuse_uses_no_tables)
6579
This happen if we are using a constant expression in the ON part
6581
SELECT * FROM a LEFT JOIN b ON b.key=30
6582
Here we should not mark the table as a 'const' as a field may
6583
have a 'normal' value or a NULL value.
6595
get_store_key(Session *session, KEYUSE *keyuse, table_map used_tables,
6596
KEY_PART_INFO *key_part, unsigned char *key_buff, uint32_t maybe_null)
6598
if (!((~used_tables) & keyuse->used_tables)) // if const item
895
6600
return new store_key_const_item(session,
896
6601
key_part->field,
897
6602
key_buff + maybe_null,
898
6603
maybe_null ? key_buff : 0,
899
6604
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))
6607
else if (keyuse->val->type() == Item::FIELD_ITEM ||
6608
(keyuse->val->type() == Item::REF_ITEM &&
6609
((Item_ref*)keyuse->val)->ref_type() == Item_ref::OUTER_REF &&
6610
(*(Item_ref**)((Item_ref*)keyuse->val)->ref)->ref_type() ==
6611
Item_ref::DIRECT_REF &&
6612
keyuse->val->real_item()->type() == Item::FIELD_ITEM))
908
6613
return new store_key_field(session,
909
6614
key_part->field,
910
6615
key_buff + maybe_null,
911
6616
maybe_null ? key_buff : 0,
912
6617
key_part->length,
913
((Item_field*) key_use_val->real_item())->field,
914
key_use_val->full_name());
6618
((Item_field*) keyuse->val->real_item())->field,
6619
keyuse->val->full_name());
916
6620
return new store_key_item(session,
917
6621
key_part->field,
918
6622
key_buff + maybe_null,
919
6623
maybe_null ? key_buff : 0,
920
6624
key_part->length,
6869
Fill in outer join related info for the execution plan structure.
6871
For each outer join operation left after simplification of the
6872
original query the function set up the following pointers in the linear
6873
structure join->join_tab representing the selected execution plan.
6874
The first inner table t0 for the operation is set to refer to the last
6875
inner table tk through the field t0->last_inner.
6876
Any inner table ti for the operation are set to refer to the first
6877
inner table ti->first_inner.
6878
The first inner table t0 for the operation is set to refer to the
6879
first inner table of the embedding outer join operation, if there is any,
6880
through the field t0->first_upper.
6881
The on expression for the outer join operation is attached to the
6882
corresponding first inner table through the field t0->on_expr_ref.
6883
Here ti are structures of the JOIN_TAB type.
6885
EXAMPLE. For the query:
6889
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
6890
ON (t1.a=t2.a AND t1.b=t3.b)
6894
given the execution plan with the table order t1,t2,t3,t4
6895
is selected, the following references will be set;
6896
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
6897
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
6898
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
6899
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
6901
@param join reference to the info fully describing the query
6904
The function assumes that the simplification procedure has been
6905
already applied to the join query (see simplify_joins).
6906
This function can be called only after the execution plan
6911
make_outerjoin_info(JOIN *join)
6913
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6915
JOIN_TAB *tab=join->join_tab+i;
6916
Table *table=tab->table;
6917
TableList *tbl= table->pos_in_table_list;
6918
TableList *embedding= tbl->embedding;
6920
if (tbl->outer_join)
6923
Table tab is the only one inner table for outer join.
6924
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
6925
is in the query above.)
6927
tab->last_inner= tab->first_inner= tab;
6928
tab->on_expr_ref= &tbl->on_expr;
6929
tab->cond_equal= tbl->cond_equal;
6931
tab->first_upper= embedding->nested_join->first_nested;
6933
for ( ; embedding ; embedding= embedding->embedding)
6935
/* Ignore sj-nests: */
6936
if (!embedding->on_expr)
6938
nested_join_st *nested_join= embedding->nested_join;
6939
if (!nested_join->counter_)
6942
Table tab is the first inner table for nested_join.
6943
Save reference to it in the nested join structure.
6945
nested_join->first_nested= tab;
6946
tab->on_expr_ref= &embedding->on_expr;
6947
tab->cond_equal= tbl->cond_equal;
6948
if (embedding->embedding)
6949
tab->first_upper= embedding->embedding->nested_join->first_nested;
6951
if (!tab->first_inner)
6952
tab->first_inner= nested_join->first_nested;
6953
if (++nested_join->counter_ < nested_join->join_list.elements)
6955
/* Table tab is the last inner table for nested join. */
6956
nested_join->first_nested->last_inner= tab;
6964
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
6966
Session *session= join->session;
6969
add_not_null_conds(join);
6970
table_map used_tables;
6971
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
6972
{ /* there may be a select without a cond. */
6973
if (join->tables > 1)
6974
cond->update_used_tables(); // Tablenr may have changed
6975
if (join->const_tables == join->tables &&
6976
session->lex->current_select->master_unit() ==
6977
&session->lex->unit) // not upper level SELECT
6978
join->const_table_map|=RAND_TABLE_BIT;
6979
{ // Check const tables
6981
make_cond_for_table(cond,
6982
join->const_table_map,
6984
for (JOIN_TAB *tab= join->join_tab+join->const_tables;
6985
tab < join->join_tab+join->tables ; tab++)
6987
if (*tab->on_expr_ref)
6989
JOIN_TAB *cond_tab= tab->first_inner;
6990
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
6991
join->const_table_map,
6995
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
6998
tmp->quick_fix_field();
6999
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
7000
new Item_cond_and(cond_tab->select_cond,
7002
if (!cond_tab->select_cond)
7004
cond_tab->select_cond->quick_fix_field();
7007
if (const_cond && !const_cond->val_int())
7009
return(1); // Impossible const condition
7013
used_tables=((select->const_tables=join->const_table_map) |
7014
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7015
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
7017
JOIN_TAB *tab=join->join_tab+i;
7019
first_inner is the X in queries like:
7020
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
7022
JOIN_TAB *first_inner_tab= tab->first_inner;
7023
table_map current_map= tab->table->map;
7024
bool use_quick_range=0;
7028
Following force including random expression in last table condition.
7029
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
7031
if (i == join->tables-1)
7032
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
7033
used_tables|=current_map;
7035
if (tab->type == JT_REF && tab->quick &&
7036
(uint32_t) tab->ref.key == tab->quick->index &&
7037
tab->ref.key_length < tab->quick->max_used_key_length)
7039
/* Range uses longer key; Use this instead of ref on key */
7044
tab->ref.key_parts=0; // Don't use ref key.
7045
join->best_positions[i].records_read= rows2double(tab->quick->records);
7047
We will use join cache here : prevent sorting of the first
7048
table only and sort at the end.
7050
if (i != join->const_tables && join->tables > join->const_tables + 1)
7056
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
7057
if (cond && !tmp && tab->quick)
7059
if (tab->type != JT_ALL)
7062
Don't use the quick method
7063
We come here in the case where we have 'key=constant' and
7064
the test is removed by make_cond_for_table()
7072
Hack to handle the case where we only refer to a table
7073
in the ON part of an OUTER JOIN. In this case we want the code
7074
below to check if we should use 'quick' instead.
7076
tmp= new Item_int((int64_t) 1,1); // Always true
7080
if (tmp || !cond || tab->type == JT_REF || tab->type == JT_REF_OR_NULL ||
7081
tab->type == JT_EQ_REF)
7083
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
7084
session->memdup((unsigned char*) select,
7087
return(1); // End of memory
7089
If tab is an inner table of an outer join operation,
7090
add a match guard to the pushed down predicate.
7091
The guard will turn the predicate on only after
7092
the first match for outer tables is encountered.
7097
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
7098
a cond, so neutralize the hack above.
7100
if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
7102
tab->select_cond=sel->cond=tmp;
7103
/* Push condition to storage engine if this is enabled
7104
and the condition is not guarded */
7105
tab->table->file->pushed_cond= NULL;
7106
if (session->variables.engine_condition_pushdown)
7109
make_cond_for_table(tmp, current_map, current_map, 0);
7112
/* Push condition to handler */
7113
if (!tab->table->file->cond_push(push_cond))
7114
tab->table->file->pushed_cond= push_cond;
7119
tab->select_cond= sel->cond= NULL;
7121
sel->head=tab->table;
7124
/* Use quick key read if it's a constant and it's not used
7126
if (tab->needed_reg.is_clear_all() && tab->type != JT_EQ_REF
7127
&& (tab->type != JT_REF || (uint32_t) tab->ref.key == tab->quick->index))
7129
sel->quick=tab->quick; // Use value from get_quick_...
7130
sel->quick_keys.clear_all();
7131
sel->needed_reg.clear_all();
7139
uint32_t ref_key=(uint32_t) sel->head->reginfo.join_tab->ref.key+1;
7140
if (i == join->const_tables && ref_key)
7142
if (!tab->const_keys.is_clear_all() &&
7143
tab->table->reginfo.impossible_range)
7146
else if (tab->type == JT_ALL && ! use_quick_range)
7148
if (!tab->const_keys.is_clear_all() &&
7149
tab->table->reginfo.impossible_range)
7150
return(1); // Impossible range
7152
We plan to scan all rows.
7153
Check again if we should use an index.
7154
We could have used an column from a previous table in
7155
the index if we are using limit and this is the first table
7158
if ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||
7159
(!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)))
7161
/* Join with outer join condition */
7162
COND *orig_cond=sel->cond;
7163
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
7166
We can't call sel->cond->fix_fields,
7167
as it will break tab->on_expr if it's AND condition
7168
(fix_fields currently removes extra AND/OR levels).
7169
Yet attributes of the just built condition are not needed.
7170
Thus we call sel->cond->quick_fix_field for safety.
7172
if (sel->cond && !sel->cond->fixed)
7173
sel->cond->quick_fix_field();
7175
if (sel->test_quick_select(session, tab->keys,
7176
used_tables & ~ current_map,
7177
(join->select_options &
7180
join->unit->select_limit_cnt), 0,
7184
Before reporting "Impossible WHERE" for the whole query
7185
we have to check isn't it only "impossible ON" instead
7187
sel->cond=orig_cond;
7188
if (!*tab->on_expr_ref ||
7189
sel->test_quick_select(session, tab->keys,
7190
used_tables & ~ current_map,
7191
(join->select_options &
7194
join->unit->select_limit_cnt),0,
7196
return(1); // Impossible WHERE
7199
sel->cond=orig_cond;
7201
/* Fix for EXPLAIN */
7203
join->best_positions[i].records_read= (double)sel->quick->records;
7207
sel->needed_reg=tab->needed_reg;
7208
sel->quick_keys.clear_all();
7210
if (!sel->quick_keys.is_subset(tab->checked_keys) ||
7211
!sel->needed_reg.is_subset(tab->checked_keys))
7213
tab->keys=sel->quick_keys;
7214
tab->keys.merge(sel->needed_reg);
7215
tab->use_quick= (!sel->needed_reg.is_clear_all() &&
7216
(select->quick_keys.is_clear_all() ||
7218
(select->quick->records >= 100L)))) ?
7220
sel->read_tables= used_tables & ~current_map;
7222
if (i != join->const_tables && tab->use_quick != 2)
7223
{ /* Read with cache */
7225
(tmp=make_cond_for_table(cond,
7226
join->const_table_map |
7230
tab->cache.select=(SQL_SELECT*)
7231
session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
7232
tab->cache.select->cond=tmp;
7233
tab->cache.select->read_tables=join->const_table_map;
7240
Push down conditions from all on expressions.
7241
Each of these conditions are guarded by a variable
7242
that turns if off just before null complemented row for
7243
outer joins is formed. Thus, the condition from an
7244
'on expression' are guaranteed not to be checked for
7245
the null complemented row.
7248
/* First push down constant conditions from on expressions */
7249
for (JOIN_TAB *join_tab= join->join_tab+join->const_tables;
7250
join_tab < join->join_tab+join->tables ; join_tab++)
7252
if (*join_tab->on_expr_ref)
7254
JOIN_TAB *cond_tab= join_tab->first_inner;
7255
tmp= make_cond_for_table(*join_tab->on_expr_ref,
7256
join->const_table_map,
7260
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
7263
tmp->quick_fix_field();
7264
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
7265
new Item_cond_and(cond_tab->select_cond,tmp);
7266
if (!cond_tab->select_cond)
7268
cond_tab->select_cond->quick_fix_field();
7272
/* Push down non-constant conditions from on expressions */
7273
JOIN_TAB *last_tab= tab;
7274
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
7277
Table tab is the last inner table of an outer join.
7278
An on expression is always attached to it.
7280
COND *on_expr= *first_inner_tab->on_expr_ref;
7282
table_map used_tables2= (join->const_table_map |
7283
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7284
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
7286
current_map= tab->table->map;
7287
used_tables2|= current_map;
7288
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
7292
JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
7294
First add the guards for match variables of
7295
all embedding outer join operations.
7297
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
7302
Now add the guard turning the predicate off for
7303
the null complemented row.
7305
tmp_cond= new Item_func_trig_cond(tmp_cond,
7309
tmp_cond->quick_fix_field();
7310
/* Add the predicate to other pushed down predicates */
7311
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
7312
new Item_cond_and(cond_tab->select_cond,
7314
if (!cond_tab->select_cond)
7316
cond_tab->select_cond->quick_fix_field();
7319
first_inner_tab= first_inner_tab->first_upper;
7328
Check if given expression uses only table fields covered by the given index
7331
uses_index_fields_only()
7332
item Expression to check
7333
tbl The table having the index
7334
keyno The index number
7335
other_tbls_ok true <=> Fields of other non-const tables are allowed
7338
Check if given expression only uses fields covered by index #keyno in the
7339
table tbl. The expression can use any fields in any other tables.
7341
The expression is guaranteed not to be AND or OR - those constructs are
7342
handled outside of this function.
7349
bool uses_index_fields_only(Item *item, Table *tbl, uint32_t keyno,
7352
if (item->const_item())
7356
Don't push down the triggered conditions. Nested outer joins execution
7357
code may need to evaluate a condition several times (both triggered and
7358
untriggered), and there is no way to put thi
7359
TODO: Consider cloning the triggered condition and using the copies for:
7360
1. push the first copy down, to have most restrictive index condition
7362
2. Put the second copy into tab->select_cond.
7364
if (item->type() == Item::FUNC_ITEM &&
7365
((Item_func*)item)->functype() == Item_func::TRIG_COND_FUNC)
7368
if (!(item->used_tables() & tbl->map))
7369
return other_tbls_ok;
7371
Item::Type item_type= item->type();
7372
switch (item_type) {
7373
case Item::FUNC_ITEM:
7375
/* This is a function, apply condition recursively to arguments */
7376
Item_func *item_func= (Item_func*)item;
7378
Item **item_end= (item_func->arguments()) + item_func->argument_count();
7379
for (child= item_func->arguments(); child != item_end; child++)
7381
if (!uses_index_fields_only(*child, tbl, keyno, other_tbls_ok))
7386
case Item::COND_ITEM:
7388
/* This is a function, apply condition recursively to arguments */
7389
List_iterator<Item> li(*((Item_cond*)item)->argument_list());
7391
while ((list_item=li++))
7393
if (!uses_index_fields_only(item, tbl, keyno, other_tbls_ok))
7398
case Item::FIELD_ITEM:
7400
Item_field *item_field= (Item_field*)item;
7401
if (item_field->field->table != tbl)
7403
return item_field->field->part_of_key.is_set(keyno);
7405
case Item::REF_ITEM:
7406
return uses_index_fields_only(item->real_item(), tbl, keyno,
7409
return false; /* Play it safe, don't push unknown non-const items */
1216
7414
#define ICP_COND_USES_INDEX_ONLY 10
1222
void JoinTable::cleanup()
1224
safe_delete(select);
7417
Get a part of the condition that can be checked using only index fields
7420
make_cond_for_index()
7421
cond The source condition
7422
table The table that is partially available
7423
keyno The index in the above table. Only fields covered by the index
7425
other_tbls_ok true <=> Fields of other non-const tables are allowed
7428
Get a part of the condition that can be checked when for the given table
7429
we have values only of fields covered by some index. The condition may
7430
refer to other tables, it is assumed that we have values of all of their
7434
make_cond_for_index(
7435
"cond(t1.field) AND cond(t2.key1) AND cond(t2.non_key) AND cond(t2.key2)",
7438
"cond(t1.field) AND cond(t2.key2)"
7441
Index condition, or NULL if no condition could be inferred.
7444
Item *make_cond_for_index(Item *cond, Table *table, uint32_t keyno,
7449
if (cond->type() == Item::COND_ITEM)
7451
uint32_t n_marked= 0;
7452
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7454
Item_cond_and *new_cond=new Item_cond_and;
7457
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7461
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7463
new_cond->argument_list()->push_back(fix);
7464
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7466
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7467
cond->marker= ICP_COND_USES_INDEX_ONLY;
7468
switch (new_cond->argument_list()->elements) {
7472
return new_cond->argument_list()->head();
7474
new_cond->quick_fix_field();
7480
Item_cond_or *new_cond=new Item_cond_or;
7483
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7487
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7490
new_cond->argument_list()->push_back(fix);
7491
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7493
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7494
cond->marker= ICP_COND_USES_INDEX_ONLY;
7495
new_cond->quick_fix_field();
7496
new_cond->top_level_item();
7501
if (!uses_index_fields_only(cond, table, keyno, other_tbls_ok))
7503
cond->marker= ICP_COND_USES_INDEX_ONLY;
7508
Item *make_cond_remainder(Item *cond, bool exclude_index)
7510
if (exclude_index && cond->marker == ICP_COND_USES_INDEX_ONLY)
7511
return 0; /* Already checked */
7513
if (cond->type() == Item::COND_ITEM)
7515
table_map tbl_map= 0;
7516
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7518
/* Create new top level AND item */
7519
Item_cond_and *new_cond=new Item_cond_and;
7522
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7526
Item *fix= make_cond_remainder(item, exclude_index);
7529
new_cond->argument_list()->push_back(fix);
7530
tbl_map |= fix->used_tables();
7533
switch (new_cond->argument_list()->elements) {
7537
return new_cond->argument_list()->head();
7539
new_cond->quick_fix_field();
7540
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7546
Item_cond_or *new_cond=new Item_cond_or;
7549
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7553
Item *fix= make_cond_remainder(item, false);
7556
new_cond->argument_list()->push_back(fix);
7557
tbl_map |= fix->used_tables();
7559
new_cond->quick_fix_field();
7560
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7561
new_cond->top_level_item();
7570
Try to extract and push the index condition
7574
tab A join tab that has tab->table->file and its condition
7576
keyno Index for which extract and push the condition
7577
other_tbls_ok true <=> Fields of other non-const tables are allowed
7580
Try to extract and push the index condition down to table handler
7583
static void push_index_cond(JOIN_TAB *tab, uint32_t keyno, bool other_tbls_ok)
7586
if (tab->table->file->index_flags(keyno, 0, 1) & HA_DO_INDEX_COND_PUSHDOWN &&
7587
tab->join->session->variables.engine_condition_pushdown)
7589
idx_cond= make_cond_for_index(tab->select_cond, tab->table, keyno,
7594
tab->pre_idx_push_select_cond= tab->select_cond;
7595
Item *idx_remainder_cond=
7596
tab->table->file->idx_cond_push(keyno, idx_cond);
7599
Disable eq_ref's "lookup cache" if we've pushed down an index
7601
TODO: This check happens to work on current ICP implementations, but
7602
there may exist a compliant implementation that will not work
7603
correctly with it. Sort this out when we stabilize the condition
7606
if (idx_remainder_cond != idx_cond)
7607
tab->ref.disable_cache= true;
7609
Item *row_cond= make_cond_remainder(tab->select_cond, true);
7613
if (!idx_remainder_cond)
7614
tab->select_cond= row_cond;
7617
tab->select_cond= new Item_cond_and(row_cond, idx_remainder_cond);
7618
tab->select_cond->quick_fix_field();
7619
((Item_cond_and*)tab->select_cond)->used_tables_cache=
7620
row_cond->used_tables() | idx_remainder_cond->used_tables();
7624
tab->select_cond= idx_remainder_cond;
7627
tab->select->cond= tab->select_cond;
7637
Determine if the set is already ordered for order_st BY, so it can
7638
disable join cache because it will change the ordering of the results.
7639
Code handles sort table that is at any location (not only first after
7640
the const tables) despite the fact that it's currently prohibited.
7641
We must disable join cache if the first non-const table alone is
7642
ordered. If there is a temp table the ordering is done as a last
7643
operation and doesn't prevent join cache usage.
7645
uint32_t make_join_orderinfo(JOIN *join)
7649
return join->tables;
7651
for (i=join->const_tables ; i < join->tables ; i++)
7653
JOIN_TAB *tab=join->join_tab+i;
7654
Table *table=tab->table;
7655
if ((table == join->sort_by_table &&
7656
(!join->order || join->skip_sort_order)) ||
7657
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
7667
Plan refinement stage: do various set ups for the executioner
7670
make_join_readinfo()
7671
join Join being processed
7672
options Join's options (checking for SELECT_DESCRIBE,
7673
SELECT_NO_JOIN_CACHE)
7674
no_jbuf_after Don't use join buffering after table with this number.
7677
Plan refinement stage: do various set ups for the executioner
7678
- set up use of join buffering
7679
- push index conditions
7680
- increment counters
7685
true - Out of memory
7689
make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
7692
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
7695
for (i=join->const_tables ; i < join->tables ; i++)
7697
JOIN_TAB *tab=join->join_tab+i;
7698
Table *table=tab->table;
7699
bool using_join_cache;
7700
tab->read_record.table= table;
7701
tab->read_record.file=table->file;
7702
tab->next_select=sub_select; /* normal select */
7704
TODO: don't always instruct first table's ref/range access method to
7705
produce sorted output.
7707
tab->sorted= sorted;
7708
sorted= 0; // only first must be sorted
7709
if (tab->insideout_match_tab)
7711
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
7716
switch (tab->type) {
7717
case JT_SYSTEM: // Only happens with left join
7718
table->status=STATUS_NO_RECORD;
7719
tab->read_first_record= join_read_system;
7720
tab->read_record.read_record= join_no_more_records;
7722
case JT_CONST: // Only happens with left join
7723
table->status=STATUS_NO_RECORD;
7724
tab->read_first_record= join_read_const;
7725
tab->read_record.read_record= join_no_more_records;
7726
if (table->covering_keys.is_set(tab->ref.key) &&
7730
table->file->extra(HA_EXTRA_KEYREAD);
7734
table->status=STATUS_NO_RECORD;
7737
delete tab->select->quick;
7738
tab->select->quick=0;
7742
tab->read_first_record= join_read_key;
7743
tab->read_record.read_record= join_no_more_records;
7744
if (table->covering_keys.is_set(tab->ref.key) &&
7748
table->file->extra(HA_EXTRA_KEYREAD);
7751
push_index_cond(tab, tab->ref.key, true);
7753
case JT_REF_OR_NULL:
7755
table->status=STATUS_NO_RECORD;
7758
delete tab->select->quick;
7759
tab->select->quick=0;
7763
if (table->covering_keys.is_set(tab->ref.key) &&
7767
table->file->extra(HA_EXTRA_KEYREAD);
7770
push_index_cond(tab, tab->ref.key, true);
7771
if (tab->type == JT_REF)
7773
tab->read_first_record= join_read_always_key;
7774
tab->read_record.read_record= tab->insideout_match_tab?
7775
join_read_next_same_diff : join_read_next_same;
7779
tab->read_first_record= join_read_always_key_or_null;
7780
tab->read_record.read_record= join_read_next_same_or_null;
7785
If previous table use cache
7786
If the incoming data set is already sorted don't use cache.
7788
table->status=STATUS_NO_RECORD;
7789
using_join_cache= false;
7790
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
7791
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
7792
!tab->insideout_match_tab)
7794
if ((options & SELECT_DESCRIBE) ||
7795
!join_init_cache(join->session,join->join_tab+join->const_tables,
7796
i-join->const_tables))
7798
using_join_cache= true;
7799
tab[-1].next_select=sub_select_cache; /* Patch previous */
7802
/* These init changes read_record */
7803
if (tab->use_quick == 2)
7805
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
7806
tab->read_first_record= join_init_quick_read_record;
7808
status_var_increment(join->session->status_var.select_range_check_count);
7812
tab->read_first_record= join_init_read_record;
7813
if (i == join->const_tables)
7815
if (tab->select && tab->select->quick)
7818
status_var_increment(join->session->status_var.select_range_count);
7822
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
7824
status_var_increment(join->session->status_var.select_scan_count);
7829
if (tab->select && tab->select->quick)
7832
status_var_increment(join->session->status_var.select_full_range_join_count);
7836
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
7838
status_var_increment(join->session->status_var.select_full_join_count);
7841
if (!table->no_keyread)
7843
if (tab->select && tab->select->quick &&
7844
tab->select->quick->index != MAX_KEY && //not index_merge
7845
table->covering_keys.is_set(tab->select->quick->index))
7848
table->file->extra(HA_EXTRA_KEYREAD);
7850
else if (!table->covering_keys.is_clear_all() &&
7851
!(tab->select && tab->select->quick))
7852
{ // Only read index tree
7853
if (!tab->insideout_match_tab)
7856
See bug #26447: "Using the clustered index for a table scan
7857
is always faster than using a secondary index".
7859
if (table->s->primary_key != MAX_KEY &&
7860
table->file->primary_key_is_clustered())
7861
tab->index= table->s->primary_key;
7863
tab->index= table->find_shortest_key(&table->covering_keys);
7865
tab->read_first_record= join_read_first;
7866
tab->type=JT_NEXT; // Read with index_first / index_next
7869
if (tab->select && tab->select->quick &&
7870
tab->select->quick->index != MAX_KEY && ! tab->table->key_read)
7871
push_index_cond(tab, tab->select->quick->index, !using_join_cache);
7875
break; /* purecov: deadcode */
7878
abort(); /* purecov: deadcode */
7881
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
7887
Give error if we some tables are done with a full join.
7889
This is used by multi_table_update and multi_table_delete when running
7892
@param join Join condition
7897
1 Error (full join used)
7900
bool error_if_full_join(JOIN *join)
7902
for (JOIN_TAB *tab=join->join_tab, *end=join->join_tab+join->tables;
7906
if (tab->type == JT_ALL && (!tab->select || !tab->select->quick))
7908
my_message(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE,
7909
ER(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE), MYF(0));
7921
void JOIN_TAB::cleanup()
1227
7927
if (cache.buff)
1229
size_t size= cache.end - cache.buff;
1230
global_join_buffer.sub(size);
1231
7928
free(cache.buff);
2515
9632
if (!(left_const && right_const) &&
2516
9633
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,
9637
resolve_const_item(session, &args[1], args[0]);
9638
func->update_used_tables();
9639
change_cond_ref_to_const(session, save_list, and_father, and_father,
9642
else if (left_const)
9644
resolve_const_item(session, &args[0], args[1]);
9645
func->update_used_tables();
9646
change_cond_ref_to_const(session, save_list, and_father, and_father,
9656
Simplify joins replacing outer joins by inner joins whenever it's
9659
The function, during a retrieval of join_list, eliminates those
9660
outer joins that can be converted into inner join, possibly nested.
9661
It also moves the on expressions for the converted outer joins
9662
and from inner joins to conds.
9663
The function also calculates some attributes for nested joins:
9667
- on_expr_dep_tables
9668
The first two attributes are used to test whether an outer join can
9669
be substituted for an inner join. The third attribute represents the
9670
relation 'to be dependent on' for tables. If table t2 is dependent
9671
on table t1, then in any evaluated execution plan table access to
9672
table t2 must precede access to table t2. This relation is used also
9673
to check whether the query contains invalid cross-references.
9674
The forth attribute is an auxiliary one and is used to calculate
9676
As the attribute dep_tables qualifies possibles orders of tables in the
9677
execution plan, the dependencies required by the straight join
9678
modifiers are reflected in this attribute as well.
9679
The function also removes all braces that can be removed from the join
9680
expression without changing its meaning.
9683
An outer join can be replaced by an inner join if the where condition
9684
or the on expression for an embedding nested join contains a conjunctive
9685
predicate rejecting null values for some attribute of the inner tables.
9689
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9691
the predicate t2.b < 5 rejects nulls.
9692
The query is converted first to:
9694
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9696
then to the equivalent form:
9698
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
9702
Similarly the following query:
9704
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
9709
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
9713
One conversion might trigger another:
9715
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
9716
LEFT JOIN t3 ON t3.b=t2.b
9717
WHERE t3 IS NOT NULL =>
9718
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
9719
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
9720
SELECT * FROM t1, t2, t3
9721
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
9724
The function removes all unnecessary braces from the expression
9725
produced by the conversions.
9728
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9730
finally is converted to:
9732
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9737
It also will remove braces from the following queries:
9739
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
9740
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
9743
The benefit of this simplification procedure is that it might return
9744
a query for which the optimizer can evaluate execution plan with more
9745
join orders. With a left join operation the optimizer does not
9746
consider any plan where one of the inner tables is before some of outer
9750
The function is implemented by a recursive procedure. On the recursive
9751
ascent all attributes are calculated, all outer joins that can be
9752
converted are replaced and then all unnecessary braces are removed.
9753
As join list contains join tables in the reverse order sequential
9754
elimination of outer joins does not require extra recursive calls.
9757
Remove all semi-joins that have are within another semi-join (i.e. have
9758
an "ancestor" semi-join nest)
9761
Here is an example of a join query with invalid cross references:
9763
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
9766
@param join reference to the query info
9767
@param join_list list representation of the join to be converted
9768
@param conds conditions to add on expressions for converted joins
9769
@param top true <=> conds is the where condition
9772
- The new condition, if success
9777
simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top,
9781
nested_join_st *nested_join;
9782
TableList *prev_table= 0;
9783
List_iterator<TableList> li(*join_list);
9786
Try to simplify join operations from join_list.
9787
The most outer join operation is checked for conversion first.
9789
while ((table= li++))
9791
table_map used_tables;
9792
table_map not_null_tables= (table_map) 0;
9794
if ((nested_join= table->nested_join))
9797
If the element of join_list is a nested join apply
9798
the procedure to its nested join list first.
9802
Item *expr= table->on_expr;
9804
If an on expression E is attached to the table,
9805
check all null rejected predicates in this expression.
9806
If such a predicate over an attribute belonging to
9807
an inner table of an embedded outer join is found,
9808
the outer join is converted to an inner join and
9809
the corresponding on expression is added to E.
9811
expr= simplify_joins(join, &nested_join->join_list,
9812
expr, false, in_sj || table->sj_on_expr);
9814
if (!table->prep_on_expr || expr != table->on_expr)
9818
table->on_expr= expr;
9819
table->prep_on_expr= expr->copy_andor_structure(join->session);
9822
nested_join->used_tables= (table_map) 0;
9823
nested_join->not_null_tables=(table_map) 0;
9824
conds= simplify_joins(join, &nested_join->join_list, conds, top,
9825
in_sj || table->sj_on_expr);
9826
used_tables= nested_join->used_tables;
9827
not_null_tables= nested_join->not_null_tables;
9831
if (!table->prep_on_expr)
9832
table->prep_on_expr= table->on_expr;
9833
used_tables= table->table->map;
9835
not_null_tables= conds->not_null_tables();
9838
if (table->embedding)
9840
table->embedding->nested_join->used_tables|= used_tables;
9841
table->embedding->nested_join->not_null_tables|= not_null_tables;
9844
if (!table->outer_join || (used_tables & not_null_tables))
9847
For some of the inner tables there are conjunctive predicates
9848
that reject nulls => the outer join can be replaced by an inner join.
9850
table->outer_join= 0;
9853
/* Add ON expression to the WHERE or upper-level ON condition. */
9856
conds= and_conds(conds, table->on_expr);
9857
conds->top_level_item();
9858
/* conds is always a new item as both cond and on_expr existed */
9859
assert(!conds->fixed);
9860
conds->fix_fields(join->session, &conds);
9863
conds= table->on_expr;
9864
table->prep_on_expr= table->on_expr= 0;
9872
Only inner tables of non-convertible outer joins
9873
remain with on_expr.
9877
table->dep_tables|= table->on_expr->used_tables();
9878
if (table->embedding)
9880
table->dep_tables&= ~table->embedding->nested_join->used_tables;
9882
Embedding table depends on tables used
9883
in embedded on expressions.
9885
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
9888
table->dep_tables&= ~table->table->map;
9893
/* The order of tables is reverse: prev_table follows table */
9894
if (prev_table->straight)
9895
prev_table->dep_tables|= used_tables;
9896
if (prev_table->on_expr)
9898
prev_table->dep_tables|= table->on_expr_dep_tables;
9899
table_map prev_used_tables= prev_table->nested_join ?
9900
prev_table->nested_join->used_tables :
9901
prev_table->table->map;
9903
If on expression contains only references to inner tables
9904
we still make the inner tables dependent on the outer tables.
9905
It would be enough to set dependency only on one outer table
9906
for them. Yet this is really a rare case.
9908
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
9909
prev_table->dep_tables|= used_tables;
9916
Flatten nested joins that can be flattened.
9917
no ON expression and not a semi-join => can be flattened.
9920
while ((table= li++))
9922
nested_join= table->nested_join;
9923
if (table->sj_on_expr && !in_sj)
9926
If this is a semi-join that is not contained within another semi-join,
9927
leave it intact (otherwise it is flattened)
9929
join->select_lex->sj_nests.push_back(table);
9931
else if (nested_join && !table->on_expr)
9934
List_iterator<TableList> it(nested_join->join_list);
9937
tbl->embedding= table->embedding;
9938
tbl->join_list= table->join_list;
9940
li.replace(nested_join->join_list);
9948
Assign each nested join structure a bit in nested_join_map.
9950
Assign each nested join structure (except "confluent" ones - those that
9951
embed only one element) a bit in nested_join_map.
9953
@param join Join being processed
9954
@param join_list List of tables
9955
@param first_unused Number of first unused bit in nested_join_map before the
9959
This function is called after simplify_joins(), when there are no
9960
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
9961
we will not run out of bits in nested_join_map.
9964
First unused bit in nested_join_map after the call.
9967
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
9968
uint32_t first_unused)
9970
List_iterator<TableList> li(*join_list);
9972
while ((table= li++))
9974
nested_join_st *nested_join;
9975
if ((nested_join= table->nested_join))
9978
It is guaranteed by simplify_joins() function that a nested join
9979
that has only one child is either
9980
- a single-table view (the child is the underlying table), or
9981
- a single-table semi-join nest
9983
We don't assign bits to such sj-nests because
9984
1. it is redundant (a "sequence" of one table cannot be interleaved
9986
2. we could run out bits in nested_join_map otherwise.
9988
if (nested_join->join_list.elements != 1)
9990
/* Don't assign bits to sj-nests */
9992
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
9993
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
9998
return(first_unused);
10003
Set nested_join_st::counter=0 in all nested joins in passed list.
10005
Recursively set nested_join_st::counter=0 for all nested joins contained in
10006
the passed join_list.
10008
@param join_list List of nested joins to process. It may also contain base
10009
tables which will be ignored.
10012
static void reset_nj_counters(List<TableList> *join_list)
10014
List_iterator<TableList> li(*join_list);
10016
while ((table= li++))
10018
nested_join_st *nested_join;
10019
if ((nested_join= table->nested_join))
10021
nested_join->counter_= 0;
10022
reset_nj_counters(&nested_join->join_list);
2538
10030
Check interleaving with an inner tables of an outer join for
3362
int safe_index_read(JoinTable *tab)
10944
SemiJoinDuplicateElimination: Weed out duplicate row combinations
10947
do_sj_dups_weedout()
10951
1 The row combination is a duplicate (discard it)
10952
0 The row combination is not a duplicate (continue)
10955
int do_sj_dups_weedout(Session *session, SJ_TMP_TABLE *sjtbl)
10958
SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
10959
SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
10960
unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;
10961
unsigned char *nulls_ptr= ptr;
10963
/* Put the the rowids tuple into table->record[0]: */
10965
// 1. Store the length
10966
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
10968
*ptr= (unsigned char)(sjtbl->rowid_len + sjtbl->null_bytes);
10973
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
10977
// 2. Zero the null bytes
10978
if (sjtbl->null_bytes)
10980
memset(ptr, 0, sjtbl->null_bytes);
10981
ptr += sjtbl->null_bytes;
10984
// 3. Put the rowids
10985
for (uint32_t i=0; tab != tab_end; tab++, i++)
10987
handler *h= tab->join_tab->table->file;
10988
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
10990
/* It's a NULL-complemented row */
10991
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
10992
memset(ptr + tab->rowid_offset, 0, h->ref_length);
10996
/* Copy the rowid value */
10997
if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
10998
h->position(tab->join_tab->table->record[0]);
10999
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
11003
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
11006
/* create_myisam_from_heap will generate error if needed */
11007
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
11008
create_myisam_from_heap(session, sjtbl->tmp_table, sjtbl->start_recinfo,
11009
&sjtbl->recinfo, error, 1))
11011
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
11019
SemiJoinDuplicateElimination: Reset the temporary table
11022
int do_sj_reset(SJ_TMP_TABLE *sj_tbl)
11024
if (sj_tbl->tmp_table)
11025
return sj_tbl->tmp_table->file->ha_delete_all_rows();
11030
Process one record of the nested loop join.
11032
This function will evaluate parts of WHERE/ON clauses that are
11033
applicable to the partial record on hand and in case of success
11034
submit this record to the next level of the nested loop.
11037
static enum_nested_loop_state
11038
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
11041
bool not_used_in_distinct=join_tab->not_used_in_distinct;
11042
ha_rows found_records=join->found_records;
11043
COND *select_cond= join_tab->select_cond;
11045
if (error > 0 || (join->session->is_error())) // Fatal error
11046
return NESTED_LOOP_ERROR;
11048
return NESTED_LOOP_NO_MORE_ROWS;
11049
if (join->session->killed) // Aborted by user
11051
join->session->send_kill_message();
11052
return NESTED_LOOP_KILLED; /* purecov: inspected */
11054
if (!select_cond || select_cond->val_int())
11057
There is no select condition or the attached pushed down
11058
condition is true => a match is found.
11061
while (join_tab->first_unmatched && found)
11064
The while condition is always false if join_tab is not
11065
the last inner join table of an outer join operation.
11067
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11069
Mark that a match for current outer table is found.
11070
This activates push down conditional predicates attached
11071
to the all inner tables of the outer join.
11073
first_unmatched->found= 1;
11074
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11076
if (tab->table->reginfo.not_exists_optimize)
11077
return NESTED_LOOP_NO_MORE_ROWS;
11078
/* Check all predicates that has just been activated. */
11080
Actually all predicates non-guarded by first_unmatched->found
11081
will be re-evaluated again. It could be fixed, but, probably,
11082
it's not worth doing now.
11084
if (tab->select_cond && !tab->select_cond->val_int())
11086
/* The condition attached to table tab is false */
11087
if (tab == join_tab)
11092
Set a return point if rejected predicate is attached
11093
not to the last table of the current nest level.
11095
join->return_tab= tab;
11096
return NESTED_LOOP_OK;
11101
Check whether join_tab is not the last inner table
11102
for another embedding outer join.
11104
if ((first_unmatched= first_unmatched->first_upper) &&
11105
first_unmatched->last_inner != join_tab)
11106
first_unmatched= 0;
11107
join_tab->first_unmatched= first_unmatched;
11110
JOIN_TAB *return_tab= join->return_tab;
11111
join_tab->found_match= true;
11112
if (join_tab->check_weed_out_table)
11114
int res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table);
11116
return NESTED_LOOP_ERROR;
11118
return NESTED_LOOP_OK;
11120
else if (join_tab->do_firstmatch)
11123
We should return to the join_tab->do_firstmatch after we have
11124
enumerated all the suffixes for current prefix row combination
11126
return_tab= join_tab->do_firstmatch;
11130
It was not just a return to lower loop level when one
11131
of the newly activated predicates is evaluated as false
11132
(See above join->return_tab= tab).
11134
join->examined_rows++;
11135
join->session->row_count++;
11139
enum enum_nested_loop_state rc;
11140
/* A match from join_tab is found for the current partial join. */
11141
rc= (*join_tab->next_select)(join, join_tab+1, 0);
11142
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11144
if (return_tab < join->return_tab)
11145
join->return_tab= return_tab;
11147
if (join->return_tab < join_tab)
11148
return NESTED_LOOP_OK;
11150
Test if this was a SELECT DISTINCT query on a table that
11151
was not in the field list; In this case we can abort if
11152
we found a row, as no new rows can be added to the result.
11154
if (not_used_in_distinct && found_records != join->found_records)
11155
return NESTED_LOOP_NO_MORE_ROWS;
11158
join_tab->read_record.file->unlock_row();
11163
The condition pushed down to the table join_tab rejects all rows
11164
with the beginning coinciding with the current partial join.
11166
join->examined_rows++;
11167
join->session->row_count++;
11168
join_tab->read_record.file->unlock_row();
11170
return NESTED_LOOP_OK;
11177
Construct a NULL complimented partial join record and feed it to the next
11178
level of the nested loop. This function is used in case we have
11179
an OUTER join and no matching record was found.
11182
static enum_nested_loop_state
11183
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab)
11186
The table join_tab is the first inner table of a outer join operation
11187
and no matches has been found for the current outer row.
11189
JOIN_TAB *last_inner_tab= join_tab->last_inner;
11190
/* Cache variables for faster loop */
11192
for ( ; join_tab <= last_inner_tab ; join_tab++)
11194
/* Change the the values of guard predicate variables. */
11195
join_tab->found= 1;
11196
join_tab->not_null_compl= 0;
11197
/* The outer row is complemented by nulls for each inner tables */
11198
restore_record(join_tab->table,s->default_values); // Make empty record
11199
mark_as_null_row(join_tab->table); // For group by without error
11200
select_cond= join_tab->select_cond;
11201
/* Check all attached conditions for inner table rows. */
11202
if (select_cond && !select_cond->val_int())
11203
return NESTED_LOOP_OK;
11207
The row complemented by nulls might be the first row
11208
of embedding outer joins.
11209
If so, perform the same actions as in the code
11210
for the first regular outer join row above.
11214
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11215
if ((first_unmatched= first_unmatched->first_upper) &&
11216
first_unmatched->last_inner != join_tab)
11217
first_unmatched= 0;
11218
join_tab->first_unmatched= first_unmatched;
11219
if (!first_unmatched)
11221
first_unmatched->found= 1;
11222
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11224
if (tab->select_cond && !tab->select_cond->val_int())
11226
join->return_tab= tab;
11227
return NESTED_LOOP_OK;
11232
The row complemented by nulls satisfies all conditions
11233
attached to inner tables.
11234
Send the row complemented by nulls to be joined with the
11237
return (*join_tab->next_select)(join, join_tab+1, 0);
11241
static enum_nested_loop_state
11242
flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skip_last)
11244
enum_nested_loop_state rc= NESTED_LOOP_OK;
11248
join_tab->table->null_row= 0;
11249
if (!join_tab->cache.records)
11250
return NESTED_LOOP_OK; /* Nothing to do */
11252
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
11253
if (join_tab->use_quick == 2)
11255
if (join_tab->select->quick)
11256
{ /* Used quick select last. reset it */
11257
delete join_tab->select->quick;
11258
join_tab->select->quick=0;
11261
/* read through all records */
11262
if ((error=join_init_read_record(join_tab)))
11264
reset_cache_write(&join_tab->cache);
11265
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
11268
for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
11270
tmp->status=tmp->table->status;
11271
tmp->table->status=0;
11274
info= &join_tab->read_record;
11277
if (join->session->killed)
11279
join->session->send_kill_message();
11280
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
11282
SQL_SELECT *select=join_tab->select;
11283
if (rc == NESTED_LOOP_OK &&
11284
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
11287
reset_cache_read(&join_tab->cache);
11288
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
11290
read_cached_record(join_tab);
11291
if (!select || !select->skip_record())
11294
if (!join_tab->check_weed_out_table ||
11295
!(res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table)))
11297
rc= (join_tab->next_select)(join,join_tab+1,0);
11298
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11300
reset_cache_write(&join_tab->cache);
11305
return NESTED_LOOP_ERROR;
11309
} while (!(error=info->read_record(info)));
11312
read_cached_record(join_tab); // Restore current record
11313
reset_cache_write(&join_tab->cache);
11314
if (error > 0) // Fatal error
11315
return NESTED_LOOP_ERROR; /* purecov: inspected */
11316
for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
11317
tmp2->table->status=tmp2->status;
11318
return NESTED_LOOP_OK;
11321
int safe_index_read(JOIN_TAB *tab)
3365
11324
Table *table= tab->table;
3366
if ((error=table->cursor->index_read_map(table->getInsertRecord(),
11325
if ((error=table->file->index_read_map(table->record[0],
3367
11326
tab->ref.key_buff,
3368
11327
make_prev_keypart_map(tab->ref.key_parts),
3369
11328
HA_READ_KEY_EXACT)))
15379
/** Allocate memory needed for other rollup functions. */
15381
bool JOIN::rollup_init()
15386
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
15387
rollup.state= ROLLUP::STATE_INITED;
15390
Create pointers to the different sum function groups
15391
These are updated by rollup_make_fields()
15393
tmp_table_param.group_parts= send_group_parts;
15395
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
15397
sizeof(List<Item>) +
15398
ref_pointer_array_size)
15399
* send_group_parts )))
15402
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
15403
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
15404
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
15407
Prepare space for field list for the different levels
15408
These will be filled up in rollup_make_fields()
15410
for (i= 0 ; i < send_group_parts ; i++)
15412
rollup.null_items[i]= new (session->mem_root) Item_null_result();
15413
List<Item> *rollup_fields= &rollup.fields[i];
15414
rollup_fields->empty();
15415
rollup.ref_pointer_arrays[i]= ref_array;
15416
ref_array+= all_fields.elements;
15418
for (i= 0 ; i < send_group_parts; i++)
15420
for (j=0 ; j < fields_list.elements ; j++)
15421
rollup.fields[i].push_back(rollup.null_items[i]);
15423
List_iterator<Item> it(all_fields);
15425
while ((item= it++))
15427
order_st *group_tmp;
15428
bool found_in_group= 0;
15430
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
15432
if (*group_tmp->item == item)
15434
item->maybe_null= 1;
15436
if (item->const_item())
15439
For ROLLUP queries each constant item referenced in GROUP BY list
15440
is wrapped up into an Item_func object yielding the same value
15441
as the constant item. The objects of the wrapper class are never
15442
considered as constant items and besides they inherit all
15443
properties of the Item_result_field class.
15444
This wrapping allows us to ensure writing constant items
15445
into temporary tables whenever the result of the ROLLUP
15446
operation has to be written into a temporary table, e.g. when
15447
ROLLUP is used together with DISTINCT in the SELECT list.
15448
Usually when creating temporary tables for a intermidiate
15449
result we do not include fields for constant expressions.
15451
Item* new_item= new Item_func_rollup_const(item);
15454
new_item->fix_fields(session, (Item **) 0);
15455
session->change_item_tree(it.ref(), new_item);
15456
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
15458
if (*tmp->item == item)
15459
session->change_item_tree(tmp->item, new_item);
15464
if (item->type() == Item::FUNC_ITEM && !found_in_group)
15466
bool changed= false;
15467
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
15470
We have to prevent creation of a field in a temporary table for
15471
an expression that contains GROUP BY attributes.
15472
Marking the expression item as 'with_sum_func' will ensure this.
15475
item->with_sum_func= 1;
15483
Fill up rollup structures with pointers to fields to use.
15485
Creates copies of item_sum items for each sum level.
15487
@param fields_arg List of all fields (hidden and real ones)
15488
@param sel_fields Pointer to selected fields
15489
@param func Store here a pointer to all fields
15493
In this case func is pointing to next not used element.
15498
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields,
15501
List_iterator_fast<Item> it(fields_arg);
15502
Item *first_field= sel_fields.head();
15506
Create field lists for the different levels
15508
The idea here is to have a separate field list for each rollup level to
15509
avoid all runtime checks of which columns should be NULL.
15511
The list is stored in reverse order to get sum function in such an order
15512
in func that it makes it easy to reset them with init_sum_functions()
15514
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15516
rollup.fields[0] will contain list where a,b,c is NULL
15517
rollup.fields[1] will contain list where b,c is NULL
15519
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
15521
sum_funcs_end[0] points to all sum functions
15522
sum_funcs_end[1] points to all sum functions, except grand totals
15526
for (level=0 ; level < send_group_parts ; level++)
15529
uint32_t pos= send_group_parts - level -1;
15530
bool real_fields= 0;
15532
List_iterator<Item> new_it(rollup.fields[pos]);
15533
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
15534
order_st *start_group;
15536
/* Point to first hidden field */
15537
Item **ref_array= ref_array_start + fields_arg.elements-1;
15539
/* Remember where the sum functions ends for the previous level */
15540
sum_funcs_end[pos+1]= *func;
15542
/* Find the start of the group for this level */
15543
for (i= 0, start_group= group_list ;
15545
start_group= start_group->next)
15549
while ((item= it++))
15551
if (item == first_field)
15553
real_fields= 1; // End of hidden fields
15554
ref_array= ref_array_start;
15557
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
15558
(!((Item_sum*) item)->depended_from() ||
15559
((Item_sum *)item)->depended_from() == select_lex))
15563
This is a top level summary function that must be replaced with
15564
a sum function that is reset for this level.
15566
NOTE: This code creates an object which is not that nice in a
15567
sub select. Fortunately it's not common to have rollup in
15570
item= item->copy_or_same(session);
15571
((Item_sum*) item)->make_unique();
15572
*(*func)= (Item_sum*) item;
15577
/* Check if this is something that is part of this group by */
15578
order_st *group_tmp;
15579
for (group_tmp= start_group, i= pos ;
15580
group_tmp ; group_tmp= group_tmp->next, i++)
15582
if (*group_tmp->item == item)
15585
This is an element that is used by the GROUP BY and should be
15586
set to NULL in this level
15588
Item_null_result *null_item= new (session->mem_root) Item_null_result();
15591
item->maybe_null= 1; // Value will be null sometimes
15592
null_item->result_field= item->get_tmp_table_field();
15601
(void) new_it++; // Point to next item
15602
new_it.replace(item); // Replace previous
15609
sum_funcs_end[0]= *func; // Point to last function
15614
Send all rollup levels higher than the current one to the client.
15618
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15621
@param idx Level we are on:
15622
- 0 = Total sum level
15623
- 1 = First group changed (a)
15624
- 2 = Second group changed (a,b)
15629
1 If send_data_failed()
15632
int JOIN::rollup_send_data(uint32_t idx)
15635
for (i= send_group_parts ; i-- > idx ; )
15637
/* Get reference pointers to sum functions in place */
15638
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15639
ref_pointer_array_size);
15640
if ((!having || having->val_int()))
15642
if (send_records < unit->select_limit_cnt && do_send_rows &&
15643
result->send_data(rollup.fields[i]))
15648
/* Restore ref_pointer_array */
15649
set_items_ref_array(current_ref_pointer_array);
15654
Write all rollup levels higher than the current one to a temp table.
15658
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
15661
@param idx Level we are on:
15662
- 0 = Total sum level
15663
- 1 = First group changed (a)
15664
- 2 = Second group changed (a,b)
15665
@param table reference to temp table
15670
1 if write_data_failed()
15673
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
15676
for (i= send_group_parts ; i-- > idx ; )
15678
/* Get reference pointers to sum functions in place */
15679
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15680
ref_pointer_array_size);
15681
if ((!having || having->val_int()))
15685
List_iterator_fast<Item> it(rollup.fields[i]);
15686
while ((item= it++))
15688
if (item->type() == Item::NULL_ITEM && item->is_result_field())
15689
item->save_in_result_field(1);
15691
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
15692
if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
15694
if (create_myisam_from_heap(session, table_arg,
15695
tmp_table_param.start_recinfo,
15696
&tmp_table_param.recinfo,
15702
/* Restore ref_pointer_array */
15703
set_items_ref_array(current_ref_pointer_array);
15708
clear results if there are not rows found for group
15709
(end_send_group/end_write_group)
15714
clear_tables(this);
15715
copy_fields(&tmp_table_param);
15719
Item_sum *func, **func_ptr= sum_funcs;
15720
while ((func= *(func_ptr++)))
15728
Send a description about what how the select will be done to stdout.
15731
void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
15732
bool distinct,const char *message)
15734
List<Item> field_list;
15735
List<Item> item_list;
15736
Session *session=join->session;
15737
select_result *result=join->result;
15738
Item *item_null= new Item_null();
15739
const CHARSET_INFO * const cs= system_charset_info;
15741
/* Don't log this into the slow query log */
15742
session->server_status&= ~(SERVER_QUERY_NO_INDEX_USED | SERVER_QUERY_NO_GOOD_INDEX_USED);
15743
join->unit->offset_limit_cnt= 0;
15746
NOTE: the number/types of items pushed into item_list must be in sync with
15747
EXPLAIN column types as they're "defined" in Session::send_explain_fields()
15751
item_list.push_back(new Item_int((int32_t)
15752
join->select_lex->select_number));
15753
item_list.push_back(new Item_string(join->select_lex->type,
15754
strlen(join->select_lex->type), cs));
15755
for (uint32_t i=0 ; i < 7; i++)
15756
item_list.push_back(item_null);
15757
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15758
item_list.push_back(item_null);
15760
item_list.push_back(new Item_string(message,strlen(message),cs));
15761
if (result->send_data(item_list))
15764
else if (join->select_lex == join->unit->fake_select_lex)
15767
here we assume that the query will return at least two rows, so we
15768
show "filesort" in EXPLAIN. Of course, sometimes we'll be wrong
15769
and no filesort will be actually done, but executing all selects in
15770
the UNION to provide precise EXPLAIN information will hardly be
15773
char table_name_buffer[NAME_LEN];
15776
item_list.push_back(new Item_null);
15778
item_list.push_back(new Item_string(join->select_lex->type,
15779
strlen(join->select_lex->type),
15783
Select_Lex *sl= join->unit->first_select();
15784
uint32_t len= 6, lastop= 0;
15785
memcpy(table_name_buffer, STRING_WITH_LEN("<union"));
15786
for (; sl && len + lastop + 5 < NAME_LEN; sl= sl->next_select())
15789
lastop= snprintf(table_name_buffer + len, NAME_LEN - len,
15790
"%u,", sl->select_number);
15792
if (sl || len + lastop >= NAME_LEN)
15794
memcpy(table_name_buffer + len, STRING_WITH_LEN("...>") + 1);
15800
table_name_buffer[len - 1]= '>'; // change ',' to '>'
15802
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15805
item_list.push_back(new Item_string(join_type_str[JT_ALL],
15806
strlen(join_type_str[JT_ALL]),
15808
/* possible_keys */
15809
item_list.push_back(item_null);
15811
item_list.push_back(item_null);
15813
item_list.push_back(item_null);
15815
item_list.push_back(item_null);
15817
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15818
item_list.push_back(item_null);
15820
item_list.push_back(item_null);
15822
if (join->unit->global_parameters->order_list.first)
15823
item_list.push_back(new Item_string("Using filesort",
15826
item_list.push_back(new Item_string("", 0, cs));
15828
if (result->send_data(item_list))
15833
table_map used_tables=0;
15834
for (uint32_t i=0 ; i < join->tables ; i++)
15836
JOIN_TAB *tab=join->join_tab+i;
15837
Table *table=tab->table;
15838
TableList *table_list= tab->table->pos_in_table_list;
15840
char buff1[512], buff2[512], buff3[512];
15841
char keylen_str_buf[64];
15842
String extra(buff, sizeof(buff),cs);
15843
char table_name_buffer[NAME_LEN];
15844
String tmp1(buff1,sizeof(buff1),cs);
15845
String tmp2(buff2,sizeof(buff2),cs);
15846
String tmp3(buff3,sizeof(buff3),cs);
15855
item_list.push_back(new Item_uint((uint32_t)
15856
join->select_lex->select_number));
15858
item_list.push_back(new Item_string(join->select_lex->type,
15859
strlen(join->select_lex->type),
15861
if (tab->type == JT_ALL && tab->select && tab->select->quick)
15863
quick_type= tab->select->quick->get_type();
15864
if ((quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) ||
15865
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
15866
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION))
15867
tab->type = JT_INDEX_MERGE;
15869
tab->type = JT_RANGE;
15872
if (table->derived_select_number)
15874
/* Derived table name generation */
15875
int len= snprintf(table_name_buffer, sizeof(table_name_buffer)-1,
15877
table->derived_select_number);
15878
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15882
TableList *real_table= table->pos_in_table_list;
15883
item_list.push_back(new Item_string(real_table->alias,
15884
strlen(real_table->alias),
15887
/* "type" column */
15888
item_list.push_back(new Item_string(join_type_str[tab->type],
15889
strlen(join_type_str[tab->type]),
15891
/* Build "possible_keys" value and add it to item_list */
15892
if (!tab->keys.is_clear_all())
15895
for (j=0 ; j < table->s->keys ; j++)
15897
if (tab->keys.is_set(j))
15901
tmp1.append(table->key_info[j].name,
15902
strlen(table->key_info[j].name),
15903
system_charset_info);
15908
item_list.push_back(new Item_string(tmp1.ptr(),tmp1.length(),cs));
15910
item_list.push_back(item_null);
15912
/* Build "key", "key_len", and "ref" values and add them to item_list */
15913
if (tab->ref.key_parts)
15915
KEY *key_info=table->key_info+ tab->ref.key;
15916
register uint32_t length;
15917
item_list.push_back(new Item_string(key_info->name,
15918
strlen(key_info->name),
15919
system_charset_info));
15920
length= int64_t2str(tab->ref.key_length, keylen_str_buf, 10) -
15922
item_list.push_back(new Item_string(keylen_str_buf, length,
15923
system_charset_info));
15924
for (store_key **ref=tab->ref.key_copy ; *ref ; ref++)
15928
tmp2.append((*ref)->name(), strlen((*ref)->name()),
15929
system_charset_info);
15931
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15933
else if (tab->type == JT_NEXT)
15935
KEY *key_info=table->key_info+ tab->index;
15936
register uint32_t length;
15937
item_list.push_back(new Item_string(key_info->name,
15938
strlen(key_info->name),cs));
15939
length= int64_t2str(key_info->key_length, keylen_str_buf, 10) -
15941
item_list.push_back(new Item_string(keylen_str_buf,
15943
system_charset_info));
15944
item_list.push_back(item_null);
15946
else if (tab->select && tab->select->quick)
15948
tab->select->quick->add_keys_and_lengths(&tmp2, &tmp3);
15949
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15950
item_list.push_back(new Item_string(tmp3.ptr(),tmp3.length(),cs));
15951
item_list.push_back(item_null);
15955
if (table_list->schema_table && table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
15957
const char *tmp_buff;
15959
if (table_list->has_db_lookup_value)
15961
f_idx= table_list->schema_table->idx_field1;
15962
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15963
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15965
if (table_list->has_table_lookup_value)
15967
if (table_list->has_db_lookup_value)
15969
f_idx= table_list->schema_table->idx_field2;
15970
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15971
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15974
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15976
item_list.push_back(item_null);
15979
item_list.push_back(item_null);
15980
item_list.push_back(item_null);
15981
item_list.push_back(item_null);
15984
/* Add "rows" field to item_list. */
15985
if (table_list->schema_table)
15988
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15989
item_list.push_back(item_null);
15991
item_list.push_back(item_null);
15995
double examined_rows;
15996
if (tab->select && tab->select->quick)
15997
examined_rows= rows2double(tab->select->quick->records);
15998
else if (tab->type == JT_NEXT || tab->type == JT_ALL)
15999
examined_rows= rows2double(tab->limit ? tab->limit :
16000
tab->table->file->records());
16002
examined_rows= join->best_positions[i].records_read;
16004
item_list.push_back(new Item_int((int64_t) (uint64_t) examined_rows,
16005
MY_INT64_NUM_DECIMAL_DIGITS));
16007
/* Add "filtered" field to item_list. */
16008
if (join->session->lex->describe & DESCRIBE_EXTENDED)
16012
f= (float) (100.0 * join->best_positions[i].records_read /
16014
item_list.push_back(new Item_float(f, 2));
16018
/* Build "Extra" field and add it to item_list. */
16019
bool key_read=table->key_read;
16020
if ((tab->type == JT_NEXT || tab->type == JT_CONST) &&
16021
table->covering_keys.is_set(tab->index))
16023
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT &&
16024
!((QUICK_ROR_INTERSECT_SELECT*)tab->select->quick)->need_to_fetch_row)
16028
item_list.push_back(new Item_string(tab->info,strlen(tab->info),cs));
16029
else if (tab->packed_info & TAB_INFO_HAVE_VALUE)
16031
if (tab->packed_info & TAB_INFO_USING_INDEX)
16032
extra.append(STRING_WITH_LEN("; Using index"));
16033
if (tab->packed_info & TAB_INFO_USING_WHERE)
16034
extra.append(STRING_WITH_LEN("; Using where"));
16035
if (tab->packed_info & TAB_INFO_FULL_SCAN_ON_NULL)
16036
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16037
/* Skip initial "; "*/
16038
const char *str= extra.ptr();
16039
uint32_t len= extra.length();
16045
item_list.push_back(new Item_string(str, len, cs));
16049
uint32_t keyno= MAX_KEY;
16050
if (tab->ref.key_parts)
16051
keyno= tab->ref.key;
16052
else if (tab->select && tab->select->quick)
16053
keyno = tab->select->quick->index;
16055
if (keyno != MAX_KEY && keyno == table->file->pushed_idx_cond_keyno &&
16056
table->file->pushed_idx_cond)
16057
extra.append(STRING_WITH_LEN("; Using index condition"));
16059
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
16060
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
16061
quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE)
16063
extra.append(STRING_WITH_LEN("; Using "));
16064
tab->select->quick->add_info_string(&extra);
16068
if (tab->use_quick == 2)
16070
/* 4 bits per 1 hex digit + terminating '\0' */
16071
char buf[MAX_KEY / 4 + 1];
16072
extra.append(STRING_WITH_LEN("; Range checked for each "
16073
"record (index map: 0x"));
16074
extra.append(tab->keys.print(buf));
16077
else if (tab->select->cond)
16079
const COND *pushed_cond= tab->table->file->pushed_cond;
16081
if (session->variables.engine_condition_pushdown && pushed_cond)
16083
extra.append(STRING_WITH_LEN("; Using where with pushed "
16085
if (session->lex->describe & DESCRIBE_EXTENDED)
16087
extra.append(STRING_WITH_LEN(": "));
16088
((COND *)pushed_cond)->print(&extra, QT_ORDINARY);
16092
extra.append(STRING_WITH_LEN("; Using where"));
16097
if (quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
16098
extra.append(STRING_WITH_LEN("; Using index for group-by"));
16100
extra.append(STRING_WITH_LEN("; Using index"));
16102
if (table->reginfo.not_exists_optimize)
16103
extra.append(STRING_WITH_LEN("; Not exists"));
16105
if (quick_type == QUICK_SELECT_I::QS_TYPE_RANGE &&
16106
!(((QUICK_RANGE_SELECT*)(tab->select->quick))->mrr_flags &
16107
HA_MRR_USE_DEFAULT_IMPL))
16109
extra.append(STRING_WITH_LEN("; Using MRR"));
16112
if (table_list->schema_table &&
16113
table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
16115
if (!table_list->table_open_method)
16116
extra.append(STRING_WITH_LEN("; Skip_open_table"));
16117
else if (table_list->table_open_method == OPEN_FRM_ONLY)
16118
extra.append(STRING_WITH_LEN("; Open_frm_only"));
16120
extra.append(STRING_WITH_LEN("; Open_full_table"));
16121
if (table_list->has_db_lookup_value &&
16122
table_list->has_table_lookup_value)
16123
extra.append(STRING_WITH_LEN("; Scanned 0 databases"));
16124
else if (table_list->has_db_lookup_value ||
16125
table_list->has_table_lookup_value)
16126
extra.append(STRING_WITH_LEN("; Scanned 1 database"));
16128
extra.append(STRING_WITH_LEN("; Scanned all databases"));
16130
if (need_tmp_table)
16133
extra.append(STRING_WITH_LEN("; Using temporary"));
16138
extra.append(STRING_WITH_LEN("; Using filesort"));
16140
if (distinct & test_all_bits(used_tables,session->used_tables))
16141
extra.append(STRING_WITH_LEN("; Distinct"));
16143
if (tab->insideout_match_tab)
16145
extra.append(STRING_WITH_LEN("; LooseScan"));
16148
if (tab->flush_weedout_table)
16149
extra.append(STRING_WITH_LEN("; Start temporary"));
16150
else if (tab->check_weed_out_table)
16151
extra.append(STRING_WITH_LEN("; End temporary"));
16152
else if (tab->do_firstmatch)
16154
extra.append(STRING_WITH_LEN("; FirstMatch("));
16155
Table *prev_table=tab->do_firstmatch->table;
16156
if (prev_table->derived_select_number)
16158
char namebuf[NAME_LEN];
16159
/* Derived table name generation */
16160
int len= snprintf(namebuf, sizeof(namebuf)-1,
16162
prev_table->derived_select_number);
16163
extra.append(namebuf, len);
16166
extra.append(prev_table->pos_in_table_list->alias);
16167
extra.append(STRING_WITH_LEN(")"));
16170
for (uint32_t part= 0; part < tab->ref.key_parts; part++)
16172
if (tab->ref.cond_guards[part])
16174
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16179
if (i > 0 && tab[-1].next_select == sub_select_cache)
16180
extra.append(STRING_WITH_LEN("; Using join buffer"));
16182
/* Skip initial "; "*/
16183
const char *str= extra.ptr();
16184
uint32_t len= extra.length();
16190
item_list.push_back(new Item_string(str, len, cs));
16192
// For next iteration
16193
used_tables|=table->map;
16194
if (result->send_data(item_list))
16198
for (Select_Lex_Unit *unit= join->select_lex->first_inner_unit();
16200
unit= unit->next_unit())
16202
if (mysql_explain_union(session, unit, result))
16209
bool mysql_explain_union(Session *session, Select_Lex_Unit *unit, select_result *result)
16212
Select_Lex *first= unit->first_select();
16214
for (Select_Lex *sl= first;
16216
sl= sl->next_select())
16218
// drop UNCACHEABLE_EXPLAIN, because it is for internal usage only
16219
uint8_t uncacheable= (sl->uncacheable & ~UNCACHEABLE_EXPLAIN);
16220
sl->type= (((&session->lex->select_lex)==sl)?
16221
(sl->first_inner_unit() || sl->next_select() ?
16222
"PRIMARY" : "SIMPLE"):
16224
((sl->linkage == DERIVED_TABLE_TYPE) ?
16226
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16227
"DEPENDENT SUBQUERY":
16228
(uncacheable?"UNCACHEABLE SUBQUERY":
16230
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16232
uncacheable?"UNCACHEABLE UNION":
16234
sl->options|= SELECT_DESCRIBE;
16236
if (unit->is_union())
16238
unit->fake_select_lex->select_number= UINT_MAX; // jost for initialization
16239
unit->fake_select_lex->type= "UNION RESULT";
16240
unit->fake_select_lex->options|= SELECT_DESCRIBE;
16241
if (!(res= unit->prepare(session, result, SELECT_NO_UNLOCK | SELECT_DESCRIBE)))
16243
res|= unit->cleanup();
16247
session->lex->current_select= first;
16248
unit->set_limit(unit->global_parameters);
16249
res= mysql_select(session, &first->ref_pointer_array,
16250
(TableList*) first->table_list.first,
16251
first->with_wild, first->item_list,
16253
first->order_list.elements +
16254
first->group_list.elements,
16255
(order_st*) first->order_list.first,
16256
(order_st*) first->group_list.first,
16258
(order_st*) session->lex->proc_list.first,
16259
first->options | session->options | SELECT_DESCRIBE,
16260
result, unit, first);
16262
return(res || session->is_error());
6257
16266
static void print_table_array(Session *session, String *str, TableList **table,
6258
16267
TableList **end)