48
45
#include <drizzled/check_stack_overrun.h>
49
46
#include <drizzled/lock.h>
50
47
#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>
77
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);
52
#if defined(CMATH_NAMESPACE)
53
using namespace CMATH_NAMESPACE;
56
const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
57
"MAYBE_REF","ALL","range","index",
58
"ref_or_null","unique_subquery","index_subquery",
62
struct st_sargable_param;
64
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
65
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds,
66
DYNAMIC_ARRAY *keyuse);
67
static bool update_ref_and_keys(Session *session, DYNAMIC_ARRAY *keyuse,
69
uint32_t tables, COND *conds,
70
COND_EQUAL *cond_equal,
71
table_map table_map, SELECT_LEX *select_lex,
72
st_sargable_param **sargables);
73
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
74
static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);
75
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
76
table_map used_tables);
77
static bool choose_plan(JOIN *join,table_map join_tables);
79
static void best_access_path(JOIN *join, JOIN_TAB *s, Session *session,
80
table_map remaining_tables, uint32_t idx,
81
double record_count, double read_time);
82
static void optimize_straight_join(JOIN *join, table_map join_tables);
83
static bool greedy_search(JOIN *join, table_map remaining_tables,
84
uint32_t depth, uint32_t prune_level);
85
static bool best_extension_by_limited_search(JOIN *join,
86
table_map remaining_tables,
87
uint32_t idx, double record_count,
88
double read_time, uint32_t depth,
89
uint32_t prune_level);
90
static uint32_t determine_search_depth(JOIN* join);
91
static int join_tab_cmp(const void* ptr1, const void* ptr2);
92
static int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
94
TODO: 'find_best' is here only temporarily until 'greedy_search' is
97
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index,
98
double record_count,double read_time);
99
static uint32_t cache_record_length(JOIN *join,uint32_t index);
100
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
101
static bool get_best_combination(JOIN *join);
102
static store_key *get_store_key(Session *session,
103
KEYUSE *keyuse, table_map used_tables,
104
KEY_PART_INFO *key_part, unsigned char *key_buff,
105
uint32_t maybe_null);
106
static bool make_simple_join(JOIN *join,Table *tmp_table);
107
static void make_outerjoin_info(JOIN *join);
108
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
109
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
110
static bool only_eq_ref_tables(JOIN *join, order_st *order, table_map tables);
111
static void update_depend_map(JOIN *join);
112
static void update_depend_map(JOIN *join, order_st *order);
113
static order_st *remove_const(JOIN *join,order_st *first_order,COND *cond,
114
bool change_list, bool *simple_order);
115
static int return_zero_rows(JOIN *join, select_result *res,TableList *tables,
116
List<Item> &fields, bool send_row,
117
uint64_t select_options, const char *info,
78
119
static COND *build_equal_items(Session *session, COND *cond,
79
120
COND_EQUAL *inherited,
80
121
List<TableList> *join_list,
81
122
COND_EQUAL **cond_equal_ref);
123
static COND* substitute_for_best_equal_field(COND *cond,
124
COND_EQUAL *cond_equal,
125
void *table_join_idx);
126
static COND *simplify_joins(JOIN *join, List<TableList> *join_list,
127
COND *conds, bool top, bool in_sj);
128
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
129
static void restore_prev_nj_state(JOIN_TAB *last);
130
static void reset_nj_counters(List<TableList> *join_list);
131
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
132
uint32_t first_unused);
135
void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);
136
static void restore_prev_sj_state(const table_map remaining_tables,
137
const JOIN_TAB *tab);
139
static COND *optimize_cond(JOIN *join, COND *conds,
140
List<TableList> *join_list,
141
Item::cond_result *cond_value);
142
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
143
static int do_select(JOIN *join,List<Item> *fields,Table *tmp_table);
145
static enum_nested_loop_state
146
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
148
static enum_nested_loop_state
149
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
150
static enum_nested_loop_state
151
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
152
static enum_nested_loop_state
153
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
154
static enum_nested_loop_state
155
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
156
static enum_nested_loop_state
157
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
158
static enum_nested_loop_state
159
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
161
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
162
static int join_read_system(JOIN_TAB *tab);
163
static int join_read_const(JOIN_TAB *tab);
164
static int join_read_key(JOIN_TAB *tab);
165
static int join_read_always_key(JOIN_TAB *tab);
166
static int join_read_last_key(JOIN_TAB *tab);
167
static int join_no_more_records(READ_RECORD *info);
168
static int join_read_next(READ_RECORD *info);
169
static int join_read_next_different(READ_RECORD *info);
170
static int join_init_quick_read_record(JOIN_TAB *tab);
171
static int test_if_quick_select(JOIN_TAB *tab);
172
static int join_init_read_record(JOIN_TAB *tab);
173
static int join_read_first(JOIN_TAB *tab);
174
static int join_read_next_same(READ_RECORD *info);
175
static int join_read_next_same_diff(READ_RECORD *info);
176
static int join_read_last(JOIN_TAB *tab);
177
static int join_read_prev_same(READ_RECORD *info);
178
static int join_read_prev(READ_RECORD *info);
179
int join_read_always_key_or_null(JOIN_TAB *tab);
180
int join_read_next_same_or_null(READ_RECORD *info);
181
static COND *make_cond_for_table(COND *cond,table_map table,
182
table_map used_table,
183
bool exclude_expensive_cond);
83
184
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);
185
static bool test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,
186
ha_rows select_limit, bool no_changes,
188
static bool list_contains_unique_index(Table *table,
189
bool (*find_func) (Field *, void *), void *data);
190
static bool find_field_in_item_list (Field *field, void *data);
191
static bool find_field_in_order_list (Field *field, void *data);
192
static int create_sort_index(Session *session, JOIN *join, order_st *order,
193
ha_rows filesort_limit, ha_rows select_limit,
195
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields,
197
static int remove_dup_with_compare(Session *session, Table *entry, Field **field,
198
uint32_t offset, Item *having);
199
static int remove_dup_with_hash_index(Session *session,Table *table,
200
uint32_t field_count, Field **first_field,
201
uint32_t key_length, Item *having);
202
static int join_init_cache(Session *session,JOIN_TAB *tables,uint32_t table_count);
203
static uint32_t used_blob_length(CACHE_FIELD **ptr);
204
static bool store_record_in_cache(JOIN_CACHE *cache);
205
static void reset_cache_read(JOIN_CACHE *cache);
206
static void reset_cache_write(JOIN_CACHE *cache);
207
static void read_cached_record(JOIN_TAB *tab);
208
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
209
static order_st *create_distinct_group(Session *session, Item **ref_pointer_array,
210
order_st *order, List<Item> &fields,
211
List<Item> &all_fields,
212
bool *all_order_by_fields_used);
213
static bool test_if_subpart(order_st *a,order_st *b);
214
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
215
static void calc_group_buffer(JOIN *join,order_st *group);
216
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
217
static bool alloc_group_fields(JOIN *join,order_st *group);
218
// Create list for using with tempory table
219
static bool change_to_use_tmp_fields(Session *session, Item **ref_pointer_array,
220
List<Item> &new_list1,
221
List<Item> &new_list2,
222
uint32_t elements, List<Item> &items);
223
// Create list for using with tempory table
224
static bool change_refs_to_tmp_fields(Session *session, Item **ref_pointer_array,
225
List<Item> &new_list1,
226
List<Item> &new_list2,
227
uint32_t elements, List<Item> &items);
228
static void init_tmptable_sum_functions(Item_sum **func);
229
static void update_tmptable_sum_func(Item_sum **func,Table *tmp_table);
230
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
231
static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab);
232
static bool setup_sum_funcs(Session *session, Item_sum **func_ptr);
233
static bool init_sum_functions(Item_sum **func, Item_sum **end);
234
static bool update_sum_func(Item_sum **func);
235
void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
236
bool distinct, const char *message=NULL);
237
static Item *remove_additional_cond(Item* conds);
238
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
239
static bool test_if_ref(Item_field *left_item,Item *right_item);
240
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
241
Item *new_cond, bool fix_fields);
93
243
static bool eval_const_cond(COND *cond)
95
245
return ((Item_func*) cond)->val_int() ? true : false;
99
250
This is used to mark equalities that were made from i-th IN-equality.
100
251
We limit semi-join InsideOut optimization to handling max 64 inequalities,
420
Function to setup clauses without sum functions.
422
inline int setup_without_group(Session *session, Item **ref_pointer_array,
426
List<Item> &all_fields,
429
order_st *group, bool *hidden_group_fields)
432
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
434
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
435
res= setup_conds(session, tables, leaves, conds);
437
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
438
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
440
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
441
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
442
group, hidden_group_fields);
443
session->lex->allow_sum_func= save_allow_sum_func;
276
447
/*****************************************************************************
277
448
Check fields, find best join, do the select and output fields.
278
select_query assumes that all tables are already opened
449
mysql_select assumes that all tables are already opened
279
450
*****************************************************************************/
453
Prepare of whole select (including sub queries in future).
456
Add check of calculation of GROUP functions and fields:
457
SELECT COUNT(*)+table.col1 from table1;
465
JOIN::prepare(Item ***rref_pointer_array,
466
TableList *tables_init,
467
uint32_t wild_num, COND *conds_init, uint32_t og_num,
468
order_st *order_init, order_st *group_init,
470
order_st *proc_param_init, SELECT_LEX *select_lex_arg,
471
SELECT_LEX_UNIT *unit_arg)
473
// to prevent double initialization on EXPLAIN
479
group_list= group_init;
481
proc_param= proc_param_init;
482
tables_list= tables_init;
483
select_lex= select_lex_arg;
484
select_lex->join= this;
485
join_list= &select_lex->top_join_list;
486
union_part= unit_arg->is_union();
488
session->lex->current_select->is_item_list_lookup= 1;
490
If we have already executed SELECT, then it have not sense to prevent
491
its table from update (see unique_table())
493
if (session->derived_tables_processing)
494
select_lex->exclude_from_table_unique_test= true;
496
/* Check that all tables, fields, conds and order are ok */
498
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
499
setup_tables_and_check_access(session, &select_lex->context, join_list,
500
tables_list, &select_lex->leaf_tables,
504
TableList *table_ptr;
505
for (table_ptr= select_lex->leaf_tables;
507
table_ptr= table_ptr->next_leaf)
510
if (setup_wild(session, tables_list, fields_list, &all_fields, wild_num) ||
511
select_lex->setup_ref_array(session, og_num) ||
512
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
514
setup_without_group(session, (*rref_pointer_array), tables_list,
515
select_lex->leaf_tables, fields_list,
516
all_fields, &conds, order, group_list,
517
&hidden_group_fields))
518
return(-1); /* purecov: inspected */
520
ref_pointer_array= *rref_pointer_array;
524
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
525
session->where="having clause";
526
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
527
select_lex->having_fix_field= 1;
528
bool having_fix_rc= (!having->fixed &&
529
(having->fix_fields(session, &having) ||
530
having->check_cols(1)));
531
select_lex->having_fix_field= 0;
532
if (having_fix_rc || session->is_error())
533
return(-1); /* purecov: inspected */
534
session->lex->allow_sum_func= save_allow_sum_func;
538
Item_subselect *subselect;
539
Item_in_subselect *in_subs= NULL;
541
Are we in a subquery predicate?
542
TODO: the block below will be executed for every PS execution without need.
544
if ((subselect= select_lex->master_unit()->item))
546
bool do_semijoin= !test(session->variables.optimizer_switch &
547
OPTIMIZER_SWITCH_NO_SEMIJOIN);
548
if (subselect->substype() == Item_subselect::IN_SUBS)
549
in_subs= (Item_in_subselect*)subselect;
552
Check if we're in subquery that is a candidate for flattening into a
553
semi-join (which is done done in flatten_subqueries()). The
555
1. Subquery predicate is an IN/=ANY subq predicate
556
2. Subquery is a single SELECT (not a UNION)
557
3. Subquery does not have GROUP BY or order_st BY
558
4. Subquery does not use aggregate functions or HAVING
559
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
560
6. No execution method was already chosen (by a prepared statement).
562
(*). We are not in a subquery of a single table UPDATE/DELETE that
563
doesn't have a JOIN (TODO: We should handle this at some
564
point by switching to multi-table UPDATE/DELETE)
566
(**). We're not in a confluent table-less subquery, like
570
!select_lex->master_unit()->first_select()->next_select() && // 2
571
!select_lex->group_list.elements && !order && // 3
572
!having && !select_lex->with_sum_func && // 4
573
session->session_marker && // 5
574
select_lex->outer_select()->join && // (*)
575
select_lex->master_unit()->first_select()->leaf_tables && // (**)
577
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
580
if (!in_subs->left_expr->fixed &&
581
in_subs->left_expr->fix_fields(session, &in_subs->left_expr))
586
Check that the right part of the subselect contains no more than one
587
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
589
if (subselect->substype() == Item_subselect::IN_SUBS &&
590
(select_lex->item_list.elements !=
591
((Item_in_subselect*)subselect)->left_expr->cols()))
593
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
598
/* Register the subquery for further processing */
599
select_lex->outer_select()->join->sj_subselects.append(session->mem_root, in_subs);
600
in_subs->expr_join_nest= (TableList*)session->session_marker;
604
bool do_materialize= !test(session->variables.optimizer_switch &
605
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
607
Check if the subquery predicate can be executed via materialization.
608
The required conditions are:
609
1. Subquery predicate is an IN/=ANY subq predicate
610
2. Subquery is a single SELECT (not a UNION)
611
3. Subquery is not a table-less query. In this case there is no
612
point in materializing.
613
4. Subquery predicate is a top-level predicate
614
(this implies it is not negated)
615
TODO: this is a limitation that should be lifeted once we
616
implement correct NULL semantics (WL#3830)
617
5. Subquery is non-correlated
619
This is an overly restrictive condition. It can be extended to:
620
(Subquery is non-correlated ||
621
Subquery is correlated to any query outer to IN predicate ||
622
(Subquery is correlated to the immediate outer query &&
623
Subquery !contains {GROUP BY, order_st BY [LIMIT],
624
aggregate functions) && subquery predicate is not under "NOT IN"))
625
6. No execution method was already chosen (by a prepared statement).
627
(*) The subquery must be part of a SELECT statement. The current
628
condition also excludes multi-table update statements.
630
We have to determine whether we will perform subquery materialization
631
before calling the IN=>EXISTS transformation, so that we know whether to
632
perform the whole transformation or only that part of it which wraps
633
Item_in_subselect in an Item_in_optimizer.
635
if (do_materialize &&
637
!select_lex->master_unit()->first_select()->next_select() && // 2
638
select_lex->master_unit()->first_select()->leaf_tables && // 3
639
session->lex->sql_command == SQLCOM_SELECT) // *
641
if (in_subs->is_top_level_item() && // 4
642
!in_subs->is_correlated && // 5
643
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
644
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
647
Item_subselect::trans_res trans_res;
648
if ((trans_res= subselect->select_transformer(this)) !=
649
Item_subselect::RES_OK)
651
return((trans_res == Item_subselect::RES_ERROR));
660
for (ord= order; ord; ord= ord->next)
662
Item *item= *ord->item;
663
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
664
item->split_sum_func(session, ref_pointer_array, all_fields);
668
if (having && having->with_sum_func)
669
having->split_sum_func(session, ref_pointer_array, all_fields,
671
if (select_lex->inner_sum_func_list)
673
Item_sum *end=select_lex->inner_sum_func_list;
674
Item_sum *item_sum= end;
677
item_sum= item_sum->next;
678
item_sum->split_sum_func(session, ref_pointer_array,
679
all_fields, item_sum->ref_by, false);
680
} while (item_sum != end);
683
if (select_lex->inner_refs_list.elements &&
684
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
688
Check if there are references to un-aggregated columns when computing
689
aggregate functions with implicit grouping (there is no GROUP BY).
691
MODE_ONLY_FULL_GROUP_BY is enabled here by default
693
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
695
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
696
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
700
/* Caclulate the number of groups */
702
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
707
goto err; /* purecov: inspected */
709
if (result && result->prepare(fields_list, unit_arg))
710
goto err; /* purecov: inspected */
712
/* Init join struct */
713
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
714
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
715
this->group= group_list != 0;
718
#ifdef RESTRICTED_GROUP
719
if (sum_func_count && !group_list && (func_count || field_count))
721
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
725
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
727
if (alloc_func_list())
733
return(-1); /* purecov: inspected */
738
Remove the predicates pushed down into the subquery
741
JOIN::remove_subq_pushed_predicates()
742
where IN Must be NULL
743
OUT The remaining WHERE condition, or NULL
746
Given that this join will be executed using (unique|index)_subquery,
747
without "checking NULL", remove the predicates that were pushed down
750
If the subquery compares scalar values, we can remove the condition that
751
was wrapped into trig_cond (it will be checked when needed by the subquery
754
If the subquery compares row values, we need to keep the wrapped
755
equalities in the WHERE clause: when the left (outer) tuple has both NULL
756
and non-NULL values, we'll do a full table scan and will rely on the
757
equalities corresponding to non-NULL parts of left tuple to filter out
758
non-matching records.
760
TODO: We can remove the equalities that will be guaranteed to be true by the
761
fact that subquery engine will be using index lookup. This must be done only
762
for cases where there are no conversion errors of significance, e.g. 257
763
that is searched in a byte. But this requires homogenization of the return
764
codes of all Field*::store() methods.
767
void JOIN::remove_subq_pushed_predicates(Item **where)
769
if (conds->type() == Item::FUNC_ITEM &&
770
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
771
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
772
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
773
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
774
((Item_func *)conds)->arguments()[0]))
282
783
Index lookup-based subquery: save some flags for EXPLAIN output
822
Check if the table's rowid is included in the temptable
825
sj_table_is_included()
827
join_tab The table to be checked
830
SemiJoinDuplicateElimination: check the table's rowid should be included
831
in the temptable. This is so if
833
1. The table is not embedded within some semi-join nest
834
2. The has been pulled out of a semi-join nest, or
836
3. The table is functionally dependent on some previous table
838
[4. This is also true for constant tables that can't be
839
NULL-complemented but this function is not called for such tables]
842
true - Include table's rowid
846
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
848
if (join_tab->emb_sj_nest)
851
/* Check if this table is functionally dependent on the tables that
852
are within the same outer join nest
854
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
855
if (join_tab->type == JT_EQ_REF)
857
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
859
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
861
JOIN_TAB *ref_tab= join->join_tab + idx;
862
if (embedding == ref_tab->table->pos_in_table_list->embedding)
865
/* Ok, functionally dependent */
868
/* Not functionally dependent => need to include*/
874
Setup the strategies to eliminate semi-join duplicates.
877
setup_semijoin_dups_elimination()
879
options Join options (needed to see if join buffering will be
881
no_jbuf_after Another bit of information re where join buffering will
885
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
888
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
890
2. FirstMatch (pick only the 1st matching row combination of inner tables)
891
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
892
together and picking the 1st one)
894
The join order has "duplicate-generating ranges", and every range is
895
served by one strategy or a combination of FirstMatch with with some
898
"Duplicate-generating range" is defined as a range within the join order
899
that contains all of the inner tables of a semi-join. All ranges must be
900
disjoint, if tables of several semi-joins are interleaved, then the ranges
901
are joined together, which is equivalent to converting
902
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
904
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
907
Applicability conditions are as follows:
909
DuplicateWeedout strategy
910
~~~~~~~~~~~~~~~~~~~~~~~~~
912
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
913
+------+ +=========================+ +---+
916
(1) - Prefix of OuterTables (those that participate in
917
IN-equality and/or are correlated with subquery) and outer
918
Noncorrelated Tables.
919
(2) - The handled range. The range starts with the first sj-inner
920
table, and covers all sj-inner and outer tables
921
Within the range, Inner, Outer, outer Noncorrelated tables
922
may follow in any order.
923
(3) - The suffix of outer Noncorrelated tables.
928
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
929
+------+ +==================+ +---+
932
(1) - Prefix of outer and non-correlated tables
933
(2) - The handled range, which may contain only inner and
934
non-correlated tables.
935
(3) - The suffix of outer Noncorrelated tables.
940
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
941
+--------+ +===========+ +=============+ +------+
944
(1) - Prefix that may contain any outer tables. The prefix must contain
945
all the non-trivially correlated outer tables. (non-trivially means
946
that the correlation is not just through the IN-equality).
948
(2) - Inner table for which the InsideOut scan is performed.
950
(3) - The remainder of the duplicate-generating range. It is served by
951
application of FirstMatch strategy, with the exception that
952
outer IN-correlated tables are considered to be non-correlated.
954
(4) - THe suffix of outer and outer non-correlated tables.
956
If several strategies are applicable, their relative priorities are:
961
This function walks over the join order and sets up the strategies by
962
setting appropriate members in join_tab structures.
966
true Out of memory error
970
int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
972
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
975
0 - invalid (EOF marker),
977
2 - Temptable (maybe confluent),
978
3 - Temptable with join buffering
981
uint32_t start_idx; /* Left range bound */
982
uint32_t end_idx; /* Right range bound */
984
For Temptable strategy: Bitmap of all outer and correlated tables from
985
all involved join nests.
987
table_map outer_tables;
988
} dups_ranges [MAX_TABLES];
990
TableList *emb_insideout_nest= NULL;
991
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
992
tables) whose ranges we're in */
993
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
994
table_map range_start_map= 0; /* table_map at current range start */
995
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
1000
First pass: locate the duplicate-generating ranges and pick the strategies.
1002
for (i=join->const_tables ; i < join->tables ; i++)
1004
JOIN_TAB *tab=join->join_tab+i;
1005
Table *table=tab->table;
1006
cur_map |= table->map;
1008
if (tab->emb_sj_nest) // Encountered an sj-inner table
1012
dups_ranges[cur_range].start_idx= i;
1013
range_start_map= cur_map & ~table->map;
1015
Remember if this is a possible start of range that is covered by
1016
the InsideOut strategy (the reason that it is not covered could
1017
be that it overlaps with anther semi-join's range. we don't
1018
support InsideOut for joined ranges)
1020
if (join->best_positions[i].use_insideout_scan)
1021
emb_insideout_nest= tab->emb_sj_nest;
1024
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
1025
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
1027
if (tab->emb_sj_nest != emb_insideout_nest)
1030
Two different semi-joins interleave. This cannot be handled by
1033
emb_insideout_nest= NULL;
1037
if (emb_sj_map) /* We're in duplicate-generating range */
1039
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
1040
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
1041
i <= no_jbuf_after && !dealing_with_jbuf)
1044
This table uses join buffering, which makes use of FirstMatch or
1045
InsideOut strategies impossible for the current and (we assume)
1046
preceding duplicate-producing ranges.
1047
That is, for the join order:
1049
x x [ x x] x [x x x] x [x x X* x] x
1051
+-----+ +-----+ | join buffering use
1054
we'll have to remove r1 and r2 and use duplicate-elimination
1055
strategy that spans all the tables, starting from the very 1st
1058
dealing_with_jbuf= true;
1059
emb_insideout_nest= false;
1062
Absorb all preceding duplicate-eliminating ranges. Their strategies
1065
for (int prev_range= 0; prev_range < cur_range; prev_range++)
1067
dups_ranges[cur_range].outer_tables |=
1068
dups_ranges[prev_range].outer_tables;
1070
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
1071
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
1076
Check if we are at the end of duplicate-producing range. We are if
1078
1. It's an InsideOut range (which presumes all correlated tables are
1079
in the prefix), and all inner tables are in the join order prefix,
1081
2. It's a DuplicateElimination range (possibly covering several
1082
SJ-nests), and all inner, outer, and correlated tables of all
1083
sj-nests are in the join order prefix.
1085
bool end_of_range= false;
1086
if (emb_insideout_nest &&
1087
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
1089
/* Save that this range is handled with InsideOut: */
1090
dups_ranges[cur_range].strategy= 1;
1093
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
1096
This is a complete range to be handled with either DuplicateWeedout
1099
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
1101
This will hold tables from within the range that need to be put
1102
into the join buffer before we can use the FirstMatch on its tail.
1104
dups_ranges[cur_range].outer_tables= emb_outer_tables &
1111
dups_ranges[cur_range].end_idx= i+1;
1112
emb_sj_map= emb_outer_tables= 0;
1113
emb_insideout_nest= NULL;
1114
dealing_with_jbuf= false;
1115
dups_ranges[++cur_range].strategy= 0;
1120
Session *session= join->session;
1121
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
1123
Second pass: setup the chosen strategies
1125
for (int j= 0; j < cur_range; j++)
1127
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
1129
if (dups_ranges[j].strategy == 1) // InsideOut strategy
1131
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
1134
else // DuplicateWeedout strategy
1136
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
1137
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
1138
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
1139
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
1140
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
1141
uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
1142
JOIN_TAB *last_outer_tab= tab - 1;
1144
Walk through the range and remember
1145
- tables that need their rowids to be put into temptable
1146
- the last outer table
1148
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1150
if (sj_table_is_included(join, tab))
1152
last_tab->join_tab= tab;
1153
last_tab->rowid_offset= jt_rowid_offset;
1154
jt_rowid_offset += tab->table->file->ref_length;
1155
if (tab->table->maybe_null)
1157
last_tab->null_byte= jt_null_bits / 8;
1158
last_tab->null_bit= jt_null_bits++;
1161
tab->table->prepare_for_position();
1162
tab->rowid_keep_flags= rowid_keep_flags;
1164
cur_map |= tab->table->map;
1165
if (!tab->emb_sj_nest && bitmap_covers(cur_map,
1166
dups_ranges[j].outer_tables))
1167
last_outer_tab= tab;
1170
if (jt_rowid_offset) /* Temptable has at least one rowid */
1172
SJ_TMP_TABLE *sjtbl;
1173
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
1174
if (!(sjtbl= (SJ_TMP_TABLE*)session->alloc(sizeof(SJ_TMP_TABLE))) ||
1175
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) session->alloc(tabs_size)))
1177
memcpy(sjtbl->tabs, sjtabs, tabs_size);
1178
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
1179
sjtbl->rowid_len= jt_rowid_offset;
1180
sjtbl->null_bits= jt_null_bits;
1181
sjtbl->null_bytes= (jt_null_bits + 7)/8;
1183
*next_sjtbl_ptr= sjtbl;
1184
next_sjtbl_ptr= &(sjtbl->next);
1188
create_duplicate_weedout_tmp_table(session,
1193
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
1194
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
1196
tab= last_outer_tab + 1;
1197
jump_to= last_outer_tab;
1200
/* Create the FirstMatch tail */
1201
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1203
if (tab->emb_sj_nest)
1204
tab->do_firstmatch= jump_to;
1213
static void cleanup_sj_tmp_tables(JOIN *join)
1215
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
1216
sj_tbl= sj_tbl->next)
1218
if (sj_tbl->tmp_table)
1220
sj_tbl->tmp_table->free_tmp_table(join->session);
1223
join->sj_tmp_tables= NULL;
1226
uint32_t make_join_orderinfo(JOIN *join);
1229
global select optimisation.
1232
error code saved in field 'error'
1243
// to prevent double initialization on EXPLAIN
1248
session->set_proc_info("optimizing");
1249
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
1250
unit->select_limit_cnt);
1251
/* select_limit is used to decide if we are likely to scan the whole table */
1252
select_limit= unit->select_limit_cnt;
1253
if (having || (select_options & OPTION_FOUND_ROWS))
1254
select_limit= HA_POS_ERROR;
1255
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
1256
// Ignore errors of execution if option IGNORE present
1257
if (session->lex->ignore)
1258
session->lex->current_select->no_error= 1;
1260
#ifdef HAVE_REF_TO_FIELDS // Not done yet
1261
/* Add HAVING to WHERE if possible */
1262
if (having && !group_list && !sum_func_count)
1269
else if ((conds=new Item_cond_and(conds,having)))
1272
Item_cond_and can't be fixed after creation, so we do not check
1275
conds->fix_fields(session, &conds);
1276
conds->change_ref_to_fields(session, tables_list);
1277
conds->top_level_item();
1283
/* Convert all outer joins to inner joins if possible */
1284
conds= simplify_joins(this, join_list, conds, true, false);
1285
build_bitmap_for_nested_joins(join_list, 0);
1287
conds= optimize_cond(this, conds, join_list, &cond_value);
1288
if (session->is_error())
1295
having= optimize_cond(this, having, join_list, &having_value);
1296
if (session->is_error())
1301
if (select_lex->where)
1302
select_lex->cond_value= cond_value;
1303
if (select_lex->having)
1304
select_lex->having_value= having_value;
1306
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
1307
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
1308
{ /* Impossible cond */
1309
zero_result_cause= having_value == Item::COND_FALSE ?
1310
"Impossible HAVING" : "Impossible WHERE";
1316
/* Optimize count(*), cmin() and cmax() */
1317
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
1321
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
1322
to the WHERE conditions,
1323
or 1 if all items were resolved,
1324
or 0, or an error number HA_ERR_...
1326
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
1328
if (res == HA_ERR_KEY_NOT_FOUND)
1330
zero_result_cause= "No matching min/max row";
1341
zero_result_cause= "No matching min/max row";
1345
zero_result_cause= "Select tables optimized away";
1346
tables_list= 0; // All tables resolved
1348
Extract all table-independent conditions and replace the WHERE
1349
clause with them. All other conditions were computed by opt_sum_query
1350
and the MIN/MAX/COUNT function(s) have been replaced by constants,
1351
so there is no need to compute the whole WHERE clause again.
1352
Notice that make_cond_for_table() will always succeed to remove all
1353
computed conditions, because opt_sum_query() is applicable only to
1355
Preserve conditions for EXPLAIN.
1357
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
1359
COND *table_independent_conds=
1360
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
1361
conds= table_independent_conds;
1370
error= -1; // Error is sent to client
1371
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
1373
/* Calculate how to do the join */
1374
session->set_proc_info("statistics");
1375
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
1376
session->is_fatal_error)
1381
/* Remove distinct if only const tables */
1382
select_distinct= select_distinct && (const_tables != tables);
1383
session->set_proc_info("preparing");
1384
if (result->initialize_tables(this))
1386
return(1); // error == -1
1388
if (const_table_map != found_const_table_map &&
1389
!(select_options & SELECT_DESCRIBE) &&
1391
!(conds->used_tables() & RAND_TABLE_BIT) ||
1392
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
1394
zero_result_cause= "no matching row in const table";
1398
if (!(session->options & OPTION_BIG_SELECTS) &&
1399
best_read > (double) session->variables.max_join_size &&
1400
!(select_options & SELECT_DESCRIBE))
1401
{ /* purecov: inspected */
1402
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
1406
if (const_tables && !session->locked_tables &&
1407
!(select_options & SELECT_NO_UNLOCK))
1408
mysql_unlock_some_tables(session, table, const_tables);
1409
if (!conds && outer_join)
1411
/* Handle the case where we have an OUTER JOIN without a WHERE */
1412
conds=new Item_int((int64_t) 1,1); // Always true
1414
select= make_select(*table, const_table_map,
1415
const_table_map, conds, 1, &error);
1417
{ /* purecov: inspected */
1418
error= -1; /* purecov: inspected */
1422
reset_nj_counters(join_list);
1423
make_outerjoin_info(this);
1426
Among the equal fields belonging to the same multiple equality
1427
choose the one that is to be retrieved first and substitute
1428
all references to these in where condition for a reference for
1433
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
1434
conds->update_used_tables();
1438
Permorm the the optimization on fields evaluation mentioned above
1439
for all on expressions.
1441
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
1443
if (*tab->on_expr_ref)
1445
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
1448
(*tab->on_expr_ref)->update_used_tables();
1452
if (conds &&!outer_join && const_table_map != found_const_table_map &&
1453
(select_options & SELECT_DESCRIBE) &&
1454
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
1456
conds=new Item_int((int64_t) 0,1); // Always false
1458
if (make_join_select(this, select, conds))
1461
"Impossible WHERE noticed after reading const tables";
1462
return(0); // error == 0
1465
error= -1; /* if goto err */
1467
/* Optimize distinct away if possible */
1469
order_st *org_order= order;
1470
order=remove_const(this, order,conds,1, &simple_order);
1471
if (session->is_error())
1478
If we are using order_st BY NULL or order_st BY const_expression,
1479
return result in any order (even if we are using a GROUP BY)
1481
if (!order && org_order)
1485
Check if we can optimize away GROUP BY/DISTINCT.
1486
We can do that if there are no aggregate functions, the
1487
fields in DISTINCT clause (if present) and/or columns in GROUP BY
1488
(if present) contain direct references to all key parts of
1489
an unique index (in whatever order) and if the key parts of the
1490
unique index cannot contain NULLs.
1491
Note that the unique keys for DISTINCT and GROUP BY should not
1492
be the same (as long as they are unique).
1494
The FROM clause must contain a single non-constant table.
1496
if (tables - const_tables == 1 && (group_list || select_distinct) &&
1497
!tmp_table_param.sum_func_count &&
1498
(!join_tab[const_tables].select ||
1499
!join_tab[const_tables].select->quick ||
1500
join_tab[const_tables].select->quick->get_type() !=
1501
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
1504
list_contains_unique_index(join_tab[const_tables].table,
1505
find_field_in_order_list,
1506
(void *) group_list))
1509
We have found that grouping can be removed since groups correspond to
1510
only one row anyway, but we still have to guarantee correct result
1511
order. The line below effectively rewrites the query from GROUP BY
1512
<fields> to order_st BY <fields>. There are two exceptions:
1513
- if skip_sort_order is set (see above), then we can simply skip
1515
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
1516
with the GROUP BY ones, i.e. either one is a prefix of another.
1517
We only check if the order_st BY is a prefix of GROUP BY. In this case
1518
test_if_subpart() copies the ASC/DESC attributes from the original
1520
If GROUP BY is a prefix of order_st BY, then it is safe to leave
1523
if (!order || test_if_subpart(group_list, order))
1524
order= skip_sort_order ? 0 : group_list;
1526
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
1527
rewritten to IGNORE INDEX FOR order_st BY(fields).
1529
join_tab->table->keys_in_use_for_order_by=
1530
join_tab->table->keys_in_use_for_group_by;
1534
if (select_distinct &&
1535
list_contains_unique_index(join_tab[const_tables].table,
1536
find_field_in_item_list,
1537
(void *) &fields_list))
1542
if (group_list || tmp_table_param.sum_func_count)
1544
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
1547
else if (select_distinct && tables - const_tables == 1)
1550
We are only using one table. In this case we change DISTINCT to a
1552
- The GROUP BY can be done through indexes (no sort) and the order_st
1553
BY only uses selected fields.
1554
(In this case we can later optimize away GROUP BY and order_st BY)
1555
- We are scanning the whole table without LIMIT
1557
- We are using CALC_FOUND_ROWS
1558
- We are using an order_st BY that can't be optimized away.
1560
We don't want to use this optimization when we are using LIMIT
1561
because in this case we can just create a temporary table that
1562
holds LIMIT rows and stop when this table is full.
1564
JOIN_TAB *tab= &join_tab[const_tables];
1565
bool all_order_fields_used;
1567
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
1568
&tab->table->keys_in_use_for_order_by);
1569
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
1570
order, fields_list, all_fields,
1571
&all_order_fields_used)))
1573
bool skip_group= (skip_sort_order &&
1574
test_if_skip_sort_order(tab, group_list, select_limit, 1,
1575
&tab->table->keys_in_use_for_group_by) != 0);
1576
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
1577
if ((skip_group && all_order_fields_used) ||
1578
select_limit == HA_POS_ERROR ||
1579
(order && !skip_sort_order))
1581
/* Change DISTINCT to GROUP BY */
1584
if (all_order_fields_used)
1586
if (order && skip_sort_order)
1589
Force MySQL to read the table in sorted order to get result in
1592
tmp_table_param.quick_group=0;
1596
group=1; // For end_write_group
1601
else if (session->is_fatal_error) // End of memory
1606
order_st *old_group_list;
1607
group_list= remove_const(this, (old_group_list= group_list), conds,
1608
rollup.state == ROLLUP::STATE_NONE,
1610
if (session->is_error())
1615
if (old_group_list && !group_list)
1618
if (!group_list && group)
1620
order=0; // The output has only one row
1622
select_distinct= 0; // No need in distinct for 1 row
1623
group_optimized_away= 1;
1626
calc_group_buffer(this, group_list);
1627
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
1629
if (test_if_subpart(group_list, order) ||
1630
(!group_list && tmp_table_param.sum_func_count))
1633
// Can't use sort on head table if using row cache
1643
Check if we need to create a temporary table.
1644
This has to be done if all tables are not already read (const tables)
1645
and one of the following conditions holds:
1646
- We are using DISTINCT (simple distinct's are already optimized away)
1647
- We are using an order_st BY or GROUP BY on fields not in the first table
1648
- We are using different order_st BY and GROUP BY orders
1649
- The user wants us to buffer the result.
1651
need_tmp= (const_tables != tables &&
1652
((select_distinct || !simple_order || !simple_group) ||
1653
(group_list && order) ||
1654
test(select_options & OPTION_BUFFER_RESULT)));
1656
uint32_t no_jbuf_after= make_join_orderinfo(this);
1657
uint64_t select_opts_for_readinfo=
1658
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
1660
sj_tmp_tables= NULL;
1661
if (!select_lex->sj_nests.is_empty())
1662
setup_semijoin_dups_elimination(this, select_opts_for_readinfo,
1665
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1666
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1669
/* Create all structures needed for materialized subquery execution. */
1670
if (setup_subquery_materialization())
1674
is this simple IN subquery?
1676
if (!group_list && !order &&
1677
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1678
tables == 1 && conds &&
1684
if (join_tab[0].type == JT_EQ_REF &&
1685
join_tab[0].ref.items[0]->name == in_left_expr_name)
1687
remove_subq_pushed_predicates(&where);
1688
save_index_subquery_explain_info(join_tab, where);
1689
join_tab[0].type= JT_UNIQUE_SUBQUERY;
1693
subselect_uniquesubquery_engine(session,
1698
else if (join_tab[0].type == JT_REF &&
1699
join_tab[0].ref.items[0]->name == in_left_expr_name)
1701
remove_subq_pushed_predicates(&where);
1702
save_index_subquery_explain_info(join_tab, where);
1703
join_tab[0].type= JT_INDEX_SUBQUERY;
1707
subselect_indexsubquery_engine(session,
1714
} else if (join_tab[0].type == JT_REF_OR_NULL &&
1715
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1716
having->name == in_having_cond)
1718
join_tab[0].type= JT_INDEX_SUBQUERY;
1720
conds= remove_additional_cond(conds);
1721
save_index_subquery_explain_info(join_tab, conds);
1723
change_engine(new subselect_indexsubquery_engine(session,
1733
Need to tell handlers that to play it safe, it should fetch all
1734
columns of the primary key of the tables: this is because MySQL may
1735
build row pointers for the rows, and for all columns of the primary key
1736
the read set has not necessarily been set by the server code.
1738
if (need_tmp || select_distinct || group_list || order)
1740
for (uint32_t i = const_tables; i < tables; i++)
1741
join_tab[i].table->prepare_for_position();
1744
if (const_tables != tables)
1747
Because filesort always does a full table scan or a quick range scan
1748
we must add the removed reference to the select for the table.
1749
We only need to do this when we have a simple_order or simple_group
1750
as in other cases the join is done before the sort.
1752
if ((order || group_list) &&
1753
(join_tab[const_tables].type != JT_ALL) &&
1754
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
1755
((order && simple_order) || (group_list && simple_group)))
1757
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
1762
if (!(select_options & SELECT_BIG_RESULT) &&
1765
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1766
unit->select_limit_cnt, 0,
1767
&join_tab[const_tables].table->
1768
keys_in_use_for_group_by))) ||
1770
tmp_table_param.quick_group)
1772
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1777
Force using of tmp table if sorting by a SP or UDF function due to
1778
their expensive and probably non-deterministic nature.
1780
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1782
Item *item= *tmp_order->item;
1783
if (item->is_expensive())
1785
/* Force tmp table without sort */
1786
need_tmp=1; simple_order=simple_group=0;
1794
if (select_options & SELECT_DESCRIBE)
1802
The loose index scan access method guarantees that all grouping or
1803
duplicate row elimination (for distinct) is already performed
1804
during data retrieval, and that all MIN/MAX functions are already
1805
computed for each group. Thus all MIN/MAX functions should be
1806
treated as regular functions, and there is no need to perform
1807
grouping in the main execution loop.
1808
Notice that currently loose index scan is applicable only for
1809
single table queries, thus it is sufficient to test only the first
1810
join_tab element of the plan for its access method.
1812
if (join_tab->is_using_loose_index_scan())
1813
tmp_table_param.precomputed_group_by= true;
1815
/* Create a tmp table if distinct or if the sort is too complicated */
1818
session->set_proc_info("Creating tmp table");
1820
init_items_ref_array();
1822
tmp_table_param.hidden_field_count= (all_fields.elements -
1823
fields_list.elements);
1824
order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1827
Pushing LIMIT to the temporary table creation is not applicable
1828
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1829
there are aggregate functions, because in all these cases we need
1832
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1834
!session->lex->current_select->with_sum_func) ?
1835
select_limit : HA_POS_ERROR;
1837
if (!(exec_tmp_table1=
1838
create_tmp_table(session, &tmp_table_param, all_fields,
1840
group_list ? 0 : select_distinct,
1841
group_list && simple_group,
1850
We don't have to store rows in temp table that doesn't match HAVING if:
1851
- we are sorting the table and writing complete group rows to the
1853
- We are using DISTINCT without resolving the distinct as a GROUP BY
1856
If having is not handled here, it will be checked before the row
1857
is sent to the client.
1860
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1863
/* if group or order on first table, sort first */
1864
if (group_list && simple_group)
1866
session->set_proc_info("Sorting for group");
1867
if (create_sort_index(session, this, group_list,
1868
HA_POS_ERROR, HA_POS_ERROR, false) ||
1869
alloc_group_fields(this, group_list) ||
1870
make_sum_func_list(all_fields, fields_list, 1) ||
1871
setup_sum_funcs(session, sum_funcs))
1879
if (make_sum_func_list(all_fields, fields_list, 0) ||
1880
setup_sum_funcs(session, sum_funcs))
1885
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1887
session->set_proc_info("Sorting for order");
1888
if (create_sort_index(session, this, order,
1889
HA_POS_ERROR, HA_POS_ERROR, true))
1898
Optimize distinct when used on some of the tables
1899
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1900
In this case we can stop scanning t2 when we have found one t1.a
1903
if (exec_tmp_table1->distinct)
1905
table_map used_tables= session->used_tables;
1906
JOIN_TAB *last_join_tab= join_tab+tables-1;
1909
if (used_tables & last_join_tab->table->map)
1911
last_join_tab->not_used_in_distinct=1;
1912
} while (last_join_tab-- != join_tab);
1913
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1914
if (order && skip_sort_order)
1916
/* Should always succeed */
1917
if (test_if_skip_sort_order(&join_tab[const_tables],
1918
order, unit->select_limit_cnt, 0,
1919
&join_tab[const_tables].table->
1920
keys_in_use_for_order_by))
1926
If this join belongs to an uncacheable subquery save
1929
if (select_lex->uncacheable && !is_top_level_join() &&
1930
init_save_join_tab())
1931
return(-1); /* purecov: inspected */
1940
Restore values in temporary join.
1942
void JOIN::restore_tmp()
1944
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1951
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1952
select_lex->offset_limit->val_uint() :
1957
if (exec_tmp_table1)
1959
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1960
exec_tmp_table1->file->ha_delete_all_rows();
1961
free_io_cache(exec_tmp_table1);
1962
filesort_free_buffers(exec_tmp_table1,0);
1964
if (exec_tmp_table2)
1966
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1967
exec_tmp_table2->file->ha_delete_all_rows();
1968
free_io_cache(exec_tmp_table2);
1969
filesort_free_buffers(exec_tmp_table2,0);
1972
set_items_ref_array(items0);
1975
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1980
/* Reset of sum functions */
1983
Item_sum *func, **func_ptr= sum_funcs;
1984
while ((func= *(func_ptr++)))
1992
@brief Save the original join layout
1994
@details Saves the original join layout so it can be reused in
1995
re-execution and for EXPLAIN.
1997
@return Operation status
1999
@retval 1 error occurred.
2003
JOIN::init_save_join_tab()
2005
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
2006
return 1; /* purecov: inspected */
2007
error= 0; // Ensure that tmp_join.error= 0
2014
JOIN::save_join_tab()
2016
if (!join_tab_save && select_lex->master_unit()->uncacheable)
2018
if (!(join_tab_save= (JOIN_TAB*)session->memdup((unsigned char*) join_tab,
2019
sizeof(JOIN_TAB) * tables)))
2030
Note, that create_sort_index calls test_if_skip_sort_order and may
2031
finally replace sorting with index scan if there is a LIMIT clause in
2032
the query. It's never shown in EXPLAIN!
2035
When can we have here session->net.report_error not zero?
2040
List<Item> *columns_list= &fields_list;
2043
session->set_proc_info("executing");
2045
(void) result->prepare2(); // Currently, this cannot fail.
2047
if (!tables_list && (tables || !select_lex->with_sum_func))
2048
{ // Only test of functions
2049
if (select_options & SELECT_DESCRIBE)
2050
select_describe(this, false, false, false,
2051
(zero_result_cause?zero_result_cause:"No tables used"));
2054
result->send_fields(*columns_list,
2055
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2057
We have to test for 'conds' here as the WHERE may not be constant
2058
even if we don't have any tables for prepared statements or if
2059
conds uses something like 'rand()'.
2061
if (cond_value != Item::COND_FALSE &&
2062
(!conds || conds->val_int()) &&
2063
(!having || having->val_int()))
2065
if (do_send_rows && result->send_data(fields_list))
2069
error= (int) result->send_eof();
2070
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 :
2071
session->sent_row_count);
2076
error=(int) result->send_eof();
2080
/* Single select (without union) always returns 0 or 1 row */
2081
session->limit_found_rows= send_records;
2082
session->examined_row_count= 0;
2086
Don't reset the found rows count if there're no tables as
2087
FOUND_ROWS() may be called. Never reset the examined row count here.
2088
It must be accumulated from all join iterations of all join parts.
2091
session->limit_found_rows= 0;
2093
if (zero_result_cause)
2095
(void) return_zero_rows(this, result, select_lex->leaf_tables,
2097
send_row_on_empty_set(),
2104
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) &&
2105
get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
2108
if (select_options & SELECT_DESCRIBE)
2111
Check if we managed to optimize order_st BY away and don't use temporary
2112
table to resolve order_st BY: in that case, we only may need to do
2113
filesort for GROUP BY.
2115
if (!order && !no_order && (!skip_sort_order || !need_tmp))
2118
Reset 'order' to 'group_list' and reinit variables describing
2122
simple_order= simple_group;
2126
(order != group_list || !(select_options & SELECT_BIG_RESULT)) &&
2127
(const_tables == tables ||
2128
((simple_order || skip_sort_order) &&
2129
test_if_skip_sort_order(&join_tab[const_tables], order,
2131
&join_tab[const_tables].table->
2132
keys_in_use_for_query))))
2135
select_describe(this, need_tmp,
2136
order != 0 && !skip_sort_order,
2138
!tables ? "No tables used" : NULL);
2142
JOIN *curr_join= this;
2143
List<Item> *curr_all_fields= &all_fields;
2144
List<Item> *curr_fields_list= &fields_list;
2145
Table *curr_tmp_table= 0;
2147
Initialize examined rows here because the values from all join parts
2148
must be accumulated in examined_row_count. Hence every join
2149
iteration must count from zero.
2151
curr_join->examined_rows= 0;
2153
/* Create a tmp table if distinct or if the sort is too complicated */
2159
We are in a non cacheable sub query. Get the saved join structure
2161
(curr_join may have been modified during last exection and we need
2164
curr_join= tmp_join;
2166
curr_tmp_table= exec_tmp_table1;
2168
/* Copy data to the temporary table */
2169
session->set_proc_info("Copying to tmp table");
2170
if (!curr_join->sort_and_group &&
2171
curr_join->const_tables != curr_join->tables)
2172
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2173
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2178
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
2180
if (curr_join->having)
2181
curr_join->having= curr_join->tmp_having= 0; // Allready done
2183
/* Change sum_fields reference to calculated fields in tmp_table */
2184
curr_join->all_fields= *curr_all_fields;
2187
items1= items0 + all_fields.elements;
2188
if (sort_and_group || curr_tmp_table->group)
2190
if (change_to_use_tmp_fields(session, items1,
2191
tmp_fields_list1, tmp_all_fields1,
2192
fields_list.elements, all_fields))
2197
if (change_refs_to_tmp_fields(session, items1,
2198
tmp_fields_list1, tmp_all_fields1,
2199
fields_list.elements, all_fields))
2202
curr_join->tmp_all_fields1= tmp_all_fields1;
2203
curr_join->tmp_fields_list1= tmp_fields_list1;
2204
curr_join->items1= items1;
2206
curr_all_fields= &tmp_all_fields1;
2207
curr_fields_list= &tmp_fields_list1;
2208
curr_join->set_items_ref_array(items1);
2210
if (sort_and_group || curr_tmp_table->group)
2212
curr_join->tmp_table_param.field_count+=
2213
curr_join->tmp_table_param.sum_func_count+
2214
curr_join->tmp_table_param.func_count;
2215
curr_join->tmp_table_param.sum_func_count=
2216
curr_join->tmp_table_param.func_count= 0;
2220
curr_join->tmp_table_param.field_count+=
2221
curr_join->tmp_table_param.func_count;
2222
curr_join->tmp_table_param.func_count= 0;
2225
if (curr_tmp_table->group)
2226
{ // Already grouped
2227
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
2228
curr_join->order= curr_join->group_list; /* order by group */
2229
curr_join->group_list= 0;
2233
If we have different sort & group then we must sort the data by group
2234
and copy it to another tmp table
2235
This code is also used if we are using distinct something
2236
we haven't been able to store in the temporary table yet
2237
like SEC_TO_TIME(SUM(...)).
2240
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))
2241
{ /* Must copy to another table */
2242
/* Free first data from old join */
2243
curr_join->join_free();
2244
if (make_simple_join(curr_join, curr_tmp_table))
2246
calc_group_buffer(curr_join, group_list);
2247
count_field_types(select_lex, &curr_join->tmp_table_param,
2248
curr_join->tmp_all_fields1,
2249
curr_join->select_distinct && !curr_join->group_list);
2250
curr_join->tmp_table_param.hidden_field_count=
2251
(curr_join->tmp_all_fields1.elements-
2252
curr_join->tmp_fields_list1.elements);
2255
if (exec_tmp_table2)
2256
curr_tmp_table= exec_tmp_table2;
2259
/* group data to new table */
2262
If the access method is loose index scan then all MIN/MAX
2263
functions are precomputed, and should be treated as regular
2264
functions. See extended comment in JOIN::exec.
2266
if (curr_join->join_tab->is_using_loose_index_scan())
2267
curr_join->tmp_table_param.precomputed_group_by= true;
2269
if (!(curr_tmp_table=
2270
exec_tmp_table2= create_tmp_table(session,
2271
&curr_join->tmp_table_param,
2274
curr_join->select_distinct &&
2275
!curr_join->group_list,
2276
1, curr_join->select_options,
2280
curr_join->exec_tmp_table2= exec_tmp_table2;
2282
if (curr_join->group_list)
2284
session->set_proc_info("Creating sort index");
2285
if (curr_join->join_tab == join_tab && save_join_tab())
2289
if (create_sort_index(session, curr_join, curr_join->group_list,
2290
HA_POS_ERROR, HA_POS_ERROR, false) ||
2291
make_group_fields(this, curr_join))
2295
sortorder= curr_join->sortorder;
2298
session->set_proc_info("Copying to group table");
2300
if (curr_join != this)
2304
curr_join->sum_funcs= sum_funcs2;
2305
curr_join->sum_funcs_end= sum_funcs_end2;
2309
curr_join->alloc_func_list();
2310
sum_funcs2= curr_join->sum_funcs;
2311
sum_funcs_end2= curr_join->sum_funcs_end;
2314
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2317
curr_join->group_list= 0;
2318
if (!curr_join->sort_and_group &&
2319
curr_join->const_tables != curr_join->tables)
2320
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2321
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2322
(tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2327
end_read_record(&curr_join->join_tab->read_record);
2328
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
2329
curr_join->join_tab[0].table= 0; // Table is freed
2331
// No sum funcs anymore
2334
items2= items1 + all_fields.elements;
2335
if (change_to_use_tmp_fields(session, items2,
2336
tmp_fields_list2, tmp_all_fields2,
2337
fields_list.elements, tmp_all_fields1))
2339
curr_join->tmp_fields_list2= tmp_fields_list2;
2340
curr_join->tmp_all_fields2= tmp_all_fields2;
2342
curr_fields_list= &curr_join->tmp_fields_list2;
2343
curr_all_fields= &curr_join->tmp_all_fields2;
2344
curr_join->set_items_ref_array(items2);
2345
curr_join->tmp_table_param.field_count+=
2346
curr_join->tmp_table_param.sum_func_count;
2347
curr_join->tmp_table_param.sum_func_count= 0;
2349
if (curr_tmp_table->distinct)
2350
curr_join->select_distinct=0; /* Each row is unique */
2352
curr_join->join_free(); /* Free quick selects */
2353
if (curr_join->select_distinct && ! curr_join->group_list)
2355
session->set_proc_info("Removing duplicates");
2356
if (curr_join->tmp_having)
2357
curr_join->tmp_having->update_used_tables();
2358
if (remove_duplicates(curr_join, curr_tmp_table,
2359
*curr_fields_list, curr_join->tmp_having))
2361
curr_join->tmp_having=0;
2362
curr_join->select_distinct=0;
2364
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
2365
if (make_simple_join(curr_join, curr_tmp_table))
2367
calc_group_buffer(curr_join, curr_join->group_list);
2368
count_field_types(select_lex, &curr_join->tmp_table_param,
2369
*curr_all_fields, 0);
2373
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
2375
if (make_group_fields(this, curr_join))
2382
init_items_ref_array();
2383
items3= ref_pointer_array + (all_fields.elements*4);
2384
setup_copy_fields(session, &curr_join->tmp_table_param,
2385
items3, tmp_fields_list3, tmp_all_fields3,
2386
curr_fields_list->elements, *curr_all_fields);
2387
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
2388
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
2389
tmp_table_param.save_copy_field_end=
2390
curr_join->tmp_table_param.copy_field_end;
2391
curr_join->tmp_all_fields3= tmp_all_fields3;
2392
curr_join->tmp_fields_list3= tmp_fields_list3;
2396
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
2397
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
2398
curr_join->tmp_table_param.copy_field_end=
2399
tmp_table_param.save_copy_field_end;
2401
curr_fields_list= &tmp_fields_list3;
2402
curr_all_fields= &tmp_all_fields3;
2403
curr_join->set_items_ref_array(items3);
2405
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2407
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2408
session->is_fatal_error)
2411
if (curr_join->group_list || curr_join->order)
2413
session->set_proc_info("Sorting result");
2414
/* If we have already done the group, add HAVING to sorted table */
2415
if (curr_join->tmp_having && ! curr_join->group_list &&
2416
! curr_join->sort_and_group)
2418
// Some tables may have been const
2419
curr_join->tmp_having->update_used_tables();
2420
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
2421
table_map used_tables= (curr_join->const_table_map |
2422
curr_table->table->map);
2424
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having,
2427
if (sort_table_cond)
2429
if (!curr_table->select)
2430
if (!(curr_table->select= new SQL_SELECT))
2432
if (!curr_table->select->cond)
2433
curr_table->select->cond= sort_table_cond;
2434
else // This should never happen
2436
if (!(curr_table->select->cond=
2437
new Item_cond_and(curr_table->select->cond,
2441
Item_cond_and do not need fix_fields for execution, its parameters
2442
are fixed or do not need fix_fields, too
2444
curr_table->select->cond->quick_fix_field();
2446
curr_table->select_cond= curr_table->select->cond;
2447
curr_table->select_cond->top_level_item();
2448
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
2455
curr_join->select_limit= HA_POS_ERROR;
2459
We can abort sorting after session->select_limit rows if we there is no
2460
WHERE clause for any tables after the sorted one.
2462
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
2463
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
2464
for (; curr_table < end_table ; curr_table++)
2467
table->keyuse is set in the case there was an original WHERE clause
2468
on the table that was optimized away.
2470
if (curr_table->select_cond ||
2471
(curr_table->keyuse && !curr_table->first_inner))
2473
/* We have to sort all rows */
2474
curr_join->select_limit= HA_POS_ERROR;
2479
if (curr_join->join_tab == join_tab && save_join_tab())
2484
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
2485
chose FILESORT to be faster than INDEX SCAN or there is no
2486
suitable index present.
2487
Note, that create_sort_index calls test_if_skip_sort_order and may
2488
finally replace sorting with index scan if there is a LIMIT clause in
2489
the query. XXX: it's never shown in EXPLAIN!
2490
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
2492
if (create_sort_index(session, curr_join,
2493
curr_join->group_list ?
2494
curr_join->group_list : curr_join->order,
2495
curr_join->select_limit,
2496
(select_options & OPTION_FOUND_ROWS ?
2497
HA_POS_ERROR : unit->select_limit_cnt),
2498
curr_join->group_list ? true : false))
2500
sortorder= curr_join->sortorder;
2501
if (curr_join->const_tables != curr_join->tables &&
2502
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
2505
If no IO cache exists for the first table then we are using an
2506
INDEX SCAN and no filesort. Thus we should not remove the sorted
2507
attribute on the INDEX SCAN.
2513
/* XXX: When can we have here session->is_error() not zero? */
2514
if (session->is_error())
2516
error= session->is_error();
2519
curr_join->having= curr_join->tmp_having;
2520
curr_join->fields= curr_fields_list;
2523
session->set_proc_info("Sending data");
2524
result->send_fields(*curr_fields_list,
2525
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2526
error= do_select(curr_join, curr_fields_list, NULL);
2527
session->limit_found_rows= curr_join->send_records;
2530
/* Accumulate the counts from all join iterations of all join parts. */
2531
session->examined_row_count+= curr_join->examined_rows;
2534
With EXPLAIN EXTENDED we have to restore original ref_array
2535
for a derived table which is always materialized.
2536
Otherwise we would not be able to print the query correctly.
2539
(session->lex->describe & DESCRIBE_EXTENDED) &&
2540
select_lex->linkage == DERIVED_TABLE_TYPE)
2541
set_items_ref_array(items0);
2551
Return error that hold JOIN.
2557
select_lex->join= 0;
2561
if (join_tab != tmp_join->join_tab)
2563
JOIN_TAB *tab, *end;
2564
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
2567
tmp_join->tmp_join= 0;
2568
tmp_table_param.copy_field=0;
2569
return(tmp_join->destroy());
2574
if (exec_tmp_table1)
2575
exec_tmp_table1->free_tmp_table(session);
2576
if (exec_tmp_table2)
2577
exec_tmp_table2->free_tmp_table(session);
2579
delete_dynamic(&keyuse);
317
2586
An entry point to single-unit select (a select without UNION).
319
@param session thread Cursor
2588
@param session thread handler
320
2589
@param rref_pointer_array a reference to ref_pointer_array of
321
2590
the top-level select_lex for this query
322
2591
@param tables list of all tables used in this query.
452
2722
return(join->error);
455
inline Item *and_items(Item* cond, Item *item)
2726
int subq_sj_candidate_cmp(Item_in_subselect* const *el1,
2727
Item_in_subselect* const *el2)
2729
return ((*el1)->sj_convert_priority < (*el2)->sj_convert_priority) ? 1 :
2730
( ((*el1)->sj_convert_priority == (*el2)->sj_convert_priority)? 0 : -1);
2734
inline Item * and_items(Item* cond, Item *item)
457
2736
return (cond? (new Item_cond_and(cond, item)) : item);
2740
static TableList *alloc_join_nest(Session *session)
2743
if (!(tbl= (TableList*) session->calloc(ALIGN_SIZE(sizeof(TableList))+
2744
sizeof(nested_join_st))))
2746
tbl->nested_join= (nested_join_st*) ((unsigned char*)tbl +
2747
ALIGN_SIZE(sizeof(TableList)));
2752
void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TableList> *tlist)
2754
List_iterator<TableList> it(*tlist);
2756
while ((table= it++))
2759
table->on_expr->fix_after_pullout(new_parent, &table->on_expr);
2760
if (table->nested_join)
2761
fix_list_after_tbl_changes(new_parent, &table->nested_join->join_list);
2767
Convert a subquery predicate into a TableList semi-join nest
2770
convert_subq_to_sj()
2771
parent_join Parent join, the one that has subq_pred in its WHERE/ON
2773
subq_pred Subquery predicate to be converted
2776
Convert a subquery predicate into a TableList semi-join nest. All the
2777
prerequisites are already checked, so the conversion is always successfull.
2779
Prepared Statements: the transformation is permanent:
2780
- Changes in TableList structures are naturally permanent
2781
- Item tree changes are performed on statement MEM_ROOT:
2782
= we activate statement MEM_ROOT
2783
= this function is called before the first fix_prepare_information
2786
This is intended because the criteria for subquery-to-sj conversion remain
2787
constant for the lifetime of the Prepared Statement.
2791
true Out of memory error
2794
bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
2796
SELECT_LEX *parent_lex= parent_join->select_lex;
2797
TableList *emb_tbl_nest= NULL;
2798
List<TableList> *emb_join_list= &parent_lex->top_join_list;
2799
Session *session= parent_join->session;
2802
1. Find out where to put the predicate into.
2803
Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
2805
if ((void*)subq_pred->expr_join_nest != (void*)1)
2807
if (subq_pred->expr_join_nest->nested_join)
2812
... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
2814
The sj-nest will be inserted into the brackets nest.
2816
emb_tbl_nest= subq_pred->expr_join_nest;
2817
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2819
else if (!subq_pred->expr_join_nest->outer_join)
2824
... INNER JOIN tblX ON (subquery AND whatever) ...
2826
The sj-nest will be tblX's "sibling", i.e. another child of its
2827
parent. This is ok because tblX is joined as an inner join.
2829
emb_tbl_nest= subq_pred->expr_join_nest->embedding;
2831
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2833
else if (!subq_pred->expr_join_nest->nested_join)
2835
TableList *outer_tbl= subq_pred->expr_join_nest;
2836
TableList *wrap_nest;
2840
... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
2842
we'll need to convert it into:
2844
... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
2846
|<----- wrap_nest ---->|
2848
Q: other subqueries may be pointing to this element. What to do?
2849
A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
2850
But we'll need to fix other pointers.
2851
A2: Another way: have TableList::next_ptr so the following
2852
subqueries know the table has been nested.
2853
A3: changes in the TableList::outer_join will make everything work
2856
if (!(wrap_nest= alloc_join_nest(parent_join->session)))
2860
wrap_nest->embedding= outer_tbl->embedding;
2861
wrap_nest->join_list= outer_tbl->join_list;
2862
wrap_nest->alias= (char*) "(sj-wrap)";
2864
wrap_nest->nested_join->join_list.empty();
2865
wrap_nest->nested_join->join_list.push_back(outer_tbl);
2867
outer_tbl->embedding= wrap_nest;
2868
outer_tbl->join_list= &wrap_nest->nested_join->join_list;
2871
wrap_nest will take place of outer_tbl, so move the outer join flag
2874
wrap_nest->outer_join= outer_tbl->outer_join;
2875
outer_tbl->outer_join= 0;
2877
wrap_nest->on_expr= outer_tbl->on_expr;
2878
outer_tbl->on_expr= NULL;
2880
List_iterator<TableList> li(*wrap_nest->join_list);
2884
if (tbl == outer_tbl)
2886
li.replace(wrap_nest);
2891
Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
2892
semi-join nest into it
2894
emb_join_list= &wrap_nest->nested_join->join_list;
2895
emb_tbl_nest= wrap_nest;
2900
nested_join_st *nested_join;
2901
if (!(sj_nest= alloc_join_nest(parent_join->session)))
2905
nested_join= sj_nest->nested_join;
2907
sj_nest->join_list= emb_join_list;
2908
sj_nest->embedding= emb_tbl_nest;
2909
sj_nest->alias= (char*) "(sj-nest)";
2910
/* Nests do not participate in those 'chains', so: */
2911
/* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
2912
emb_join_list->push_back(sj_nest);
2915
nested_join->used_tables and nested_join->not_null_tables are
2916
initialized in simplify_joins().
2920
2. Walk through subquery's top list and set 'embedding' to point to the
2923
st_select_lex *subq_lex= subq_pred->unit->first_select();
2924
nested_join->join_list.empty();
2925
List_iterator_fast<TableList> li(subq_lex->top_join_list);
2926
TableList *tl, *last_leaf;
2929
tl->embedding= sj_nest;
2930
tl->join_list= &nested_join->join_list;
2931
nested_join->join_list.push_back(tl);
2935
Reconnect the next_leaf chain.
2936
TODO: Do we have to put subquery's tables at the end of the chain?
2937
Inserting them at the beginning would be a bit faster.
2938
NOTE: We actually insert them at the front! That's because the order is
2939
reversed in this list.
2941
for (tl= parent_lex->leaf_tables; tl->next_leaf; tl= tl->next_leaf) {};
2942
tl->next_leaf= subq_lex->leaf_tables;
2946
Same as above for next_local chain
2947
(a theory: a next_local chain always starts with ::leaf_tables
2948
because view's tables are inserted after the view)
2950
for (tl= parent_lex->leaf_tables; tl->next_local; tl= tl->next_local) {};
2951
tl->next_local= subq_lex->leaf_tables;
2953
/* A theory: no need to re-connect the next_global chain */
2955
/* 3. Remove the original subquery predicate from the WHERE/ON */
2957
// The subqueries were replaced for Item_int(1) earlier
2958
subq_pred->exec_method= Item_in_subselect::SEMI_JOIN; // for subsequent executions
2959
/*TODO: also reset the 'with_subselect' there. */
2961
/* n. Adjust the parent_join->tables counter */
2962
uint32_t table_no= parent_join->tables;
2963
/* n. Walk through child's tables and adjust table->map */
2964
for (tl= subq_lex->leaf_tables; tl; tl= tl->next_leaf, table_no++)
2966
tl->table->tablenr= table_no;
2967
tl->table->map= ((table_map)1) << table_no;
2968
SELECT_LEX *old_sl= tl->select_lex;
2969
tl->select_lex= parent_join->select_lex;
2970
for(TableList *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)
2971
emb->select_lex= parent_join->select_lex;
2973
parent_join->tables += subq_lex->join->tables;
2976
Put the subquery's WHERE into semi-join's sj_on_expr
2977
Add the subquery-induced equalities too.
2979
SELECT_LEX *save_lex= session->lex->current_select;
2980
session->lex->current_select=subq_lex;
2981
if (!subq_pred->left_expr->fixed &&
2982
subq_pred->left_expr->fix_fields(session, &subq_pred->left_expr))
2984
session->lex->current_select=save_lex;
2986
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
2987
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables() |
2988
subq_pred->left_expr->used_tables();
2989
sj_nest->sj_on_expr= subq_lex->where;
2992
Create the IN-equalities and inject them into semi-join's ON expression.
2993
Additionally, for InsideOut strategy
2994
- Record the number of IN-equalities.
2995
- Create list of pointers to (oe1, ..., ieN). We'll need the list to
2996
see which of the expressions are bound and which are not (for those
2997
we'll produce a distinct stream of (ie_i1,...ie_ik).
2999
(TODO: can we just create a list of pointers and hope the expressions
3000
will not substitute themselves on fix_fields()? or we need to wrap
3001
them into Item_direct_view_refs and store pointers to those. The
3002
pointers to Item_direct_view_refs are guaranteed to be stable as
3003
Item_direct_view_refs doesn't substitute itself with anything in
3004
Item_direct_view_ref::fix_fields.
3006
sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
3007
sj_nest->nested_join->sj_outer_expr_list.empty();
3009
if (subq_pred->left_expr->cols() == 1)
3011
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr);
3013
Item *item_eq= new Item_func_eq(subq_pred->left_expr,
3014
subq_lex->ref_pointer_array[0]);
3015
item_eq->name= (char*)subq_sj_cond_name;
3016
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3020
for (uint32_t i= 0; i < subq_pred->left_expr->cols(); i++)
3022
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->
3025
new Item_func_eq(subq_pred->left_expr->element_index(i),
3026
subq_lex->ref_pointer_array[i]);
3027
item_eq->name= (char*)subq_sj_cond_name + (i % 64);
3028
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
3031
/* Fix the created equality and AND */
3032
sj_nest->sj_on_expr->fix_fields(parent_join->session, &sj_nest->sj_on_expr);
3035
Walk through sj nest's WHERE and ON expressions and call
3036
item->fix_table_changes() for all items.
3038
sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr);
3039
fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
3042
/* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
3043
subq_lex->master_unit()->exclude_level();
3045
/* Inject sj_on_expr into the parent's WHERE or ON */
3048
emb_tbl_nest->on_expr= and_items(emb_tbl_nest->on_expr,
3049
sj_nest->sj_on_expr);
3050
emb_tbl_nest->on_expr->fix_fields(parent_join->session, &emb_tbl_nest->on_expr);
3054
/* Inject into the WHERE */
3055
parent_join->conds= and_items(parent_join->conds, sj_nest->sj_on_expr);
3056
parent_join->conds->fix_fields(parent_join->session, &parent_join->conds);
3057
parent_join->select_lex->where= parent_join->conds;
3065
Convert candidate subquery predicates to semi-joins
3068
JOIN::flatten_subqueries()
3071
Convert candidate subquery predicates to semi-joins.
3078
bool JOIN::flatten_subqueries()
3080
Item_in_subselect **in_subq;
3081
Item_in_subselect **in_subq_end;
3083
if (sj_subselects.elements() == 0)
3086
/* 1. Fix children subqueries */
3087
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
3088
in_subq != in_subq_end; in_subq++)
3090
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3091
child_join->outer_tables = child_join->tables;
3092
if (child_join->flatten_subqueries())
3094
(*in_subq)->sj_convert_priority=
3095
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
3099
2. Pick which subqueries to convert:
3100
sort the subquery array
3101
- prefer correlated subqueries over uncorrelated;
3102
- prefer subqueries that have greater number of outer tables;
3104
sj_subselects.sort(subq_sj_candidate_cmp);
3105
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
3106
/* Replace all subqueries to be flattened with Item_int(1) */
3107
for (in_subq= sj_subselects.front();
3108
in_subq != in_subq_end &&
3109
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3112
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
3116
for (in_subq= sj_subselects.front();
3117
in_subq != in_subq_end &&
3118
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3121
if (convert_subq_to_sj(this, *in_subq))
3125
/* 3. Finalize those we didn't convert */
3126
for (; in_subq!= in_subq_end; in_subq++)
3128
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3129
Item_subselect::trans_res res;
3130
(*in_subq)->changed= 0;
3131
(*in_subq)->fixed= 0;
3132
res= (*in_subq)->select_transformer(child_join);
3133
if (res == Item_subselect::RES_ERROR)
3136
(*in_subq)->changed= 1;
3137
(*in_subq)->fixed= 1;
3139
Item *substitute= (*in_subq)->substitution;
3140
bool do_fix_fields= !(*in_subq)->substitution->fixed;
3141
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
3144
//if ((*in_subq)->fix_fields(session, (*in_subq)->ref_ptr))
3147
sj_subselects.clear();
3153
Setup for execution all subqueries of a query, for which the optimizer
3154
chose hash semi-join.
3156
@details Iterate over all subqueries of the query, and if they are under an
3157
IN predicate, and the optimizer chose to compute it via hash semi-join:
3158
- try to initialize all data structures needed for the materialized execution
3159
of the IN predicate,
3160
- if this fails, then perform the IN=>EXISTS transformation which was
3161
previously blocked during JOIN::prepare.
3163
This method is part of the "code generation" query processing phase.
3165
This phase must be called after substitute_for_best_equal_field() because
3166
that function may replace items with other items from a multiple equality,
3167
and we need to reference the correct items in the index access method of the
3170
@return Operation status
3171
@retval false success.
3172
@retval true error occurred.
3175
bool JOIN::setup_subquery_materialization()
3177
for (SELECT_LEX_UNIT *un= select_lex->first_inner_unit(); un;
3178
un= un->next_unit())
3180
for (SELECT_LEX *sl= un->first_select(); sl; sl= sl->next_select())
3182
Item_subselect *subquery_predicate= sl->master_unit()->item;
3183
if (subquery_predicate &&
3184
subquery_predicate->substype() == Item_subselect::IN_SUBS)
3186
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
3187
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
3188
in_subs->setup_engine())
3198
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3201
find_eq_ref_candidate()
3202
table Table to be checked
3203
sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
3207
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3210
Check again if it is feasible to factor common parts with constant table
3214
true - There exists an eq_ref(outer-tables) candidate
3218
bool find_eq_ref_candidate(Table *table, table_map sj_inner_tables)
3220
KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
3225
while (1) /* For each key */
3228
KEY *keyinfo= table->key_info + key;
3229
key_part_map bound_parts= 0;
3230
if ((keyinfo->flags & HA_NOSAME) == HA_NOSAME)
3232
do /* For all equalities on all key parts */
3234
/* Check if this is "t.keypart = expr(outer_tables) */
3235
if (!(keyuse->used_tables & sj_inner_tables) &&
3236
!(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
3238
bound_parts |= 1 << keyuse->keypart;
3241
} while (keyuse->key == key && keyuse->table == table);
3243
if (bound_parts == PREV_BITS(uint, keyinfo->key_parts))
3245
if (keyuse->table != table)
3253
if (keyuse->table != table)
3256
while (keyuse->key == key);
3265
Pull tables out of semi-join nests, if possible
3268
pull_out_semijoin_tables()
3269
join The join where to do the semi-join flattening
3272
Try to pull tables out of semi-join nests.
3275
When this function is called, the join may have several semi-join nests
3276
(possibly within different semi-join nests), but it is guaranteed that
3277
one semi-join nest does not contain another.
3280
A table can be pulled out of the semi-join nest if
3281
- It is a constant table
3285
* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer
3287
* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.
3288
* Semi-join nests TableList::sj_inner_tables
3290
This operation is (and should be) performed at each PS execution since
3291
tables may become/cease to be constant across PS reexecutions.
3295
1 - Out of memory error
3298
int pull_out_semijoin_tables(JOIN *join)
3301
List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);
3303
/* Try pulling out of the each of the semi-joins */
3304
while ((sj_nest= sj_list_it++))
3306
/* Action #1: Mark the constant tables to be pulled out */
3307
table_map pulled_tables= 0;
3309
List_iterator<TableList> child_li(sj_nest->nested_join->join_list);
3311
while ((tbl= child_li++))
3315
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
3316
if (tbl->table->map & join->const_table_map)
3318
pulled_tables |= tbl->table->map;
3324
Action #2: Find which tables we can pull out based on
3325
update_ref_and_keys() data. Note that pulling one table out can allow
3326
us to pull out some other tables too.
3328
bool pulled_a_table;
3331
pulled_a_table= false;
3333
while ((tbl= child_li++))
3335
if (tbl->table && !(pulled_tables & tbl->table->map))
3337
if (find_eq_ref_candidate(tbl->table,
3338
sj_nest->nested_join->used_tables &
3341
pulled_a_table= true;
3342
pulled_tables |= tbl->table->map;
3346
} while (pulled_a_table);
3349
if ((sj_nest)->nested_join->used_tables == pulled_tables)
3351
(sj_nest)->sj_inner_tables= 0;
3352
while ((tbl= child_li++))
3355
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3360
/* Record the bitmap of inner tables, mark the inner tables */
3361
table_map inner_tables=(sj_nest)->nested_join->used_tables &
3363
(sj_nest)->sj_inner_tables= inner_tables;
3364
while ((tbl= child_li++))
3368
if (inner_tables & tbl->table->map)
3369
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
3371
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
460
3379
/*****************************************************************************
461
Create JoinTableS, make a guess about the table types,
3380
Create JOIN_TABS, make a guess about the table types,
462
3381
Approximate how many records will be used in each table
463
3382
*****************************************************************************/
464
ha_rows get_quick_record_count(Session *session, optimizer::SqlSelect *select, Table *table, const key_map *keys,ha_rows limit)
3385
static ha_rows get_quick_record_count(Session *session, SQL_SELECT *select,
3387
const key_map *keys,ha_rows limit)
467
3390
if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))
482
3405
return(HA_POS_ERROR); /* This shouldn't happend */
3409
This structure is used to collect info on potentially sargable
3410
predicates in order to check whether they become sargable after
3411
reading const tables.
3412
We form a bitmap of indexes that can be used for sargable predicates.
3413
Only such indexes are involved in range analysis.
3415
typedef struct st_sargable_param
3417
Field *field; /* field against which to check sargability */
3418
Item **arg_value; /* values of potential keys for lookups */
3419
uint32_t num_values; /* number of values in the above array */
3423
Calculate the best possible join and initialize the join structure.
3432
make_join_statistics(JOIN *join, TableList *tables, COND *conds,
3433
DYNAMIC_ARRAY *keyuse_array)
3437
uint32_t i,table_count,const_count,key;
3438
table_map found_const_table_map, all_table_map, found_ref, refs;
3439
key_map const_ref, eq_part;
3440
Table **table_vector;
3441
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
3442
KEYUSE *keyuse,*start_keyuse;
3443
table_map outer_join=0;
3444
SARGABLE_PARAM *sargables= 0;
3445
JOIN_TAB *stat_vector[MAX_TABLES+1];
3447
table_count=join->tables;
3448
stat=(JOIN_TAB*) join->session->calloc(sizeof(JOIN_TAB)*table_count);
3449
stat_ref=(JOIN_TAB**) join->session->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
3450
table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
3451
if (!stat || !stat_ref || !table_vector)
3452
return(1); // Eom /* purecov: inspected */
3454
join->best_ref=stat_vector;
3456
stat_end=stat+table_count;
3457
found_const_table_map= all_table_map=0;
3462
s++, tables= tables->next_leaf, i++)
3464
TableList *embedding= tables->embedding;
3467
s->const_keys.init();
3468
s->checked_keys.init();
3469
s->needed_reg.init();
3470
table_vector[i]=s->table=table=tables->table;
3471
table->pos_in_table_list= tables;
3472
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
3475
table->file->print_error(error, MYF(0));
3478
table->quick_keys.clear_all();
3479
table->reginfo.join_tab=s;
3480
table->reginfo.not_exists_optimize=0;
3481
memset(table->const_key_parts, 0,
3482
sizeof(key_part_map)*table->s->keys);
3483
all_table_map|= table->map;
3485
s->info=0; // For describe
3487
s->dependent= tables->dep_tables;
3488
s->key_dependent= 0;
3489
if (tables->schema_table)
3490
table->file->stats.records= 2;
3491
table->quick_condition_rows= table->file->stats.records;
3493
s->on_expr_ref= &tables->on_expr;
3494
if (*s->on_expr_ref)
3496
/* s is the only inner table of an outer join */
3497
if (!table->file->stats.records && !embedding)
3499
s->dependent= 0; // Ignore LEFT JOIN depend.
3500
set_position(join,const_count++,s,(KEYUSE*) 0);
3503
outer_join|= table->map;
3504
s->embedding_map= 0;
3505
for (;embedding; embedding= embedding->embedding)
3506
s->embedding_map|= embedding->nested_join->nj_map;
3509
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
3511
/* s belongs to a nested join, maybe to several embedded joins */
3512
s->embedding_map= 0;
3515
nested_join_st *nested_join= embedding->nested_join;
3516
s->embedding_map|=nested_join->nj_map;
3517
s->dependent|= embedding->dep_tables;
3518
embedding= embedding->embedding;
3519
outer_join|= nested_join->used_tables;
3524
if ((table->file->stats.records <= 1) &&
3526
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && !join->no_const_tables)
3528
set_position(join,const_count++,s,(KEYUSE*) 0);
3532
join->outer_join=outer_join;
3534
if (join->outer_join)
3537
Build transitive closure for relation 'to be dependent on'.
3538
This will speed up the plan search for many cases with outer joins,
3539
as well as allow us to catch illegal cross references/
3540
Warshall's algorithm is used to build the transitive closure.
3541
As we use bitmaps to represent the relation the complexity
3542
of the algorithm is O((number of tables)^2).
3544
for (i= 0, s= stat ; i < table_count ; i++, s++)
3546
for (uint32_t j= 0 ; j < table_count ; j++)
3548
table= stat[j].table;
3549
if (s->dependent & table->map)
3550
s->dependent |= table->reginfo.join_tab->dependent;
3553
s->table->maybe_null= 1;
3555
/* Catch illegal cross references for outer joins */
3556
for (i= 0, s= stat ; i < table_count ; i++, s++)
3558
if (s->dependent & s->table->map)
3560
join->tables=0; // Don't use join->table
3561
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
3564
s->key_dependent= s->dependent;
3568
if (conds || outer_join)
3569
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
3570
conds, join->cond_equal,
3571
~outer_join, join->select_lex, &sargables))
3574
/* Read tables with 0 or 1 rows (system tables) */
3575
join->const_table_map= 0;
3577
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
3584
join->const_table_map|=s->table->map;
3585
if ((tmp=join_read_const_table(s, p_pos)))
3588
return(1); // Fatal error
3591
found_const_table_map|= s->table->map;
3594
/* loop until no more const tables are found */
3598
more_const_tables_found:
3603
We only have to loop from stat_vector + const_count as
3604
set_position() will move all const_tables first in stat_vector
3607
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
3612
If equi-join condition by a key is null rejecting and after a
3613
substitution of a const table the key value happens to be null
3614
then we can state that there are no matches for this equi-join.
3616
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
3619
When performing an outer join operation if there are no matching rows
3620
for the single row of the outer table all the inner tables are to be
3621
null complemented and thus considered as constant tables.
3622
Here we apply this consideration to the case of outer join operations
3623
with a single inner table only because the case with nested tables
3624
would require a more thorough analysis.
3625
TODO. Apply single row substitution to null complemented inner tables
3626
for nested outer join operations.
3628
while (keyuse->table == table)
3630
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
3631
keyuse->val->is_null() && keyuse->null_rejecting)
3634
mark_as_null_row(table);
3635
found_const_table_map|= table->map;
3636
join->const_table_map|= table->map;
3637
set_position(join,const_count++,s,(KEYUSE*) 0);
3638
goto more_const_tables_found;
3644
if (s->dependent) // If dependent on some table
3646
// All dep. must be constants
3647
if (s->dependent & ~(found_const_table_map))
3649
if (table->file->stats.records <= 1L &&
3650
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
3651
!table->pos_in_table_list->embedding)
3655
join->const_table_map|=table->map;
3656
set_position(join,const_count++,s,(KEYUSE*) 0);
3657
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
3660
return(1); // Fatal error
3663
found_const_table_map|= table->map;
3667
/* check if table can be read by key or table only uses const refs */
3668
if ((keyuse=s->keyuse))
3671
while (keyuse->table == table)
3673
start_keyuse=keyuse;
3675
s->keys.set_bit(key); // QQ: remove this ?
3678
const_ref.clear_all();
3679
eq_part.clear_all();
3682
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
3684
if (!((~found_const_table_map) & keyuse->used_tables))
3685
const_ref.set_bit(keyuse->keypart);
3687
refs|=keyuse->used_tables;
3688
eq_part.set_bit(keyuse->keypart);
3691
} while (keyuse->table == table && keyuse->key == key);
3693
if (eq_part.is_prefix(table->key_info[key].key_parts) &&
3694
!table->pos_in_table_list->embedding)
3696
if ((table->key_info[key].flags & (HA_NOSAME))
3699
if (const_ref == eq_part)
3700
{ // Found everything for ref.
3704
join->const_table_map|=table->map;
3705
set_position(join,const_count++,s,start_keyuse);
3706
if (create_ref_for_key(join, s, start_keyuse,
3707
found_const_table_map))
3709
if ((tmp=join_read_const_table(s,
3710
join->positions+const_count-1)))
3713
return(1); // Fatal error
3716
found_const_table_map|= table->map;
3720
found_ref|= refs; // Table is const if all refs are const
3722
else if (const_ref == eq_part)
3723
s->const_keys.set_bit(key);
3728
} while (join->const_table_map & found_ref && ref_changed);
3731
Update info on indexes that can be used for search lookups as
3732
reading const tables may has added new sargable predicates.
3734
if (const_count && sargables)
3736
for( ; sargables->field ; sargables++)
3738
Field *field= sargables->field;
3739
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
3740
key_map possible_keys= field->key_start;
3741
possible_keys.intersect(field->table->keys_in_use_for_query);
3743
for (uint32_t j=0; j < sargables->num_values; j++)
3744
is_const&= sargables->arg_value[j]->const_item();
3746
join_tab[0].const_keys.merge(possible_keys);
3750
if (pull_out_semijoin_tables(join))
3753
/* Calc how many (possible) matched records in each table */
3755
for (s=stat ; s < stat_end ; s++)
3757
if (s->type == JT_SYSTEM || s->type == JT_CONST)
3759
/* Only one matching row */
3760
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
3763
/* Approximate found rows and time to read them */
3764
s->found_records=s->records=s->table->file->stats.records;
3765
s->read_time=(ha_rows) s->table->file->scan_time();
3768
Set a max range of how many seeks we can expect when using keys
3769
This is can't be to high as otherwise we are likely to use
3772
s->worst_seeks= cmin((double) s->found_records / 10,
3773
(double) s->read_time*3);
3774
if (s->worst_seeks < 2.0) // Fix for small tables
3778
Add to stat->const_keys those indexes for which all group fields or
3779
all select distinct fields participate in one index.
3781
add_group_and_distinct_keys(join, s);
3783
if (!s->const_keys.is_clear_all() &&
3784
!s->table->pos_in_table_list->embedding)
3788
select= make_select(s->table, found_const_table_map,
3789
found_const_table_map,
3790
*s->on_expr_ref ? *s->on_expr_ref : conds,
3794
records= get_quick_record_count(join->session, select, s->table,
3795
&s->const_keys, join->row_limit);
3796
s->quick=select->quick;
3797
s->needed_reg=select->needed_reg;
3799
if (records == 0 && s->table->reginfo.impossible_range)
3802
Impossible WHERE or ON expression
3803
In case of ON, we mark that the we match one empty NULL row.
3804
In case of WHERE, don't set found_const_table_map to get the
3805
caller to abort with a zero row result.
3807
join->const_table_map|= s->table->map;
3808
set_position(join,const_count++,s,(KEYUSE*) 0);
3810
if (*s->on_expr_ref)
3812
/* Generate empty row */
3813
s->info= "Impossible ON condition";
3814
found_const_table_map|= s->table->map;
3816
mark_as_null_row(s->table); // All fields are NULL
3819
if (records != HA_POS_ERROR)
3821
s->found_records=records;
3822
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
3828
join->join_tab=stat;
3829
join->map2table=stat_ref;
3830
join->table= join->all_tables=table_vector;
3831
join->const_tables=const_count;
3832
join->found_const_table_map=found_const_table_map;
3834
/* Find an optimal join order of the non-constant tables. */
3835
if (join->const_tables != join->tables)
3837
optimize_keyuse(join, keyuse_array);
3838
if (choose_plan(join, all_table_map & ~join->const_table_map))
3843
memcpy(join->best_positions, join->positions,
3844
sizeof(POSITION)*join->const_tables);
3845
join->best_read=1.0;
3847
/* Generate an execution plan from the found optimal join order. */
3848
return(join->session->killed || get_best_combination(join));
485
3852
/*****************************************************************************
486
3853
Check with keys are used and with tables references with tables
487
3854
Updates in stat:
490
3857
keyuse Pointer to possible keys
491
3858
*****************************************************************************/
3860
/// Used when finding key fields
3861
typedef struct key_field_t {
3863
Item *val; ///< May be empty if diff constant
3865
uint optimize; // KEY_OPTIMIZE_*
3868
If true, the condition this struct represents will not be satisfied
3871
bool null_rejecting;
3872
bool *cond_guard; /* See KEYUSE::cond_guard */
3873
uint32_t sj_pred_no; /* See KEYUSE::sj_pred_no */
3877
Merge new key definitions to old ones, remove those not used in both.
3879
This is called for OR between different levels.
3881
To be able to do 'ref_or_null' we merge a comparison of a column
3882
and 'column IS NULL' to one test. This is useful for sub select queries
3883
that are internally transformed to something like:.
3886
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
3889
KEY_FIELD::null_rejecting is processed as follows: @n
3890
result has null_rejecting=true if it is set for both ORed references.
3892
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
3893
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
3896
The result of this is that we're missing some 'ref' accesses.
3897
OptimizerTeam: Fix this
3901
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
3904
if (start == new_fields)
3905
return start; // Impossible or
3906
if (new_fields == end)
3907
return start; // No new fields, skip all
3909
KEY_FIELD *first_free=new_fields;
3911
/* Mark all found fields in old array */
3912
for (; new_fields != end ; new_fields++)
3914
for (KEY_FIELD *old=start ; old != first_free ; old++)
3916
if (old->field == new_fields->field)
3919
NOTE: below const_item() call really works as "!used_tables()", i.e.
3920
it can return false where it is feasible to make it return true.
3922
The cause is as follows: Some of the tables are already known to be
3923
const tables (the detection code is in make_join_statistics(),
3924
above the update_ref_and_keys() call), but we didn't propagate
3925
information about this: Table::const_table is not set to true, and
3926
Item::update_used_tables() hasn't been called for each item.
3927
The result of this is that we're missing some 'ref' accesses.
3928
TODO: OptimizerTeam: Fix this
3930
if (!new_fields->val->const_item())
3933
If the value matches, we can use the key reference.
3934
If not, we keep it until we have examined all new values
3936
if (old->val->eq(new_fields->val, old->field->binary()))
3938
old->level= and_level;
3939
old->optimize= ((old->optimize & new_fields->optimize &
3940
KEY_OPTIMIZE_EXISTS) |
3941
((old->optimize | new_fields->optimize) &
3942
KEY_OPTIMIZE_REF_OR_NULL));
3943
old->null_rejecting= (old->null_rejecting &&
3944
new_fields->null_rejecting);
3947
else if (old->eq_func && new_fields->eq_func &&
3948
old->val->eq_by_collation(new_fields->val,
3949
old->field->binary(),
3950
old->field->charset()))
3953
old->level= and_level;
3954
old->optimize= ((old->optimize & new_fields->optimize &
3955
KEY_OPTIMIZE_EXISTS) |
3956
((old->optimize | new_fields->optimize) &
3957
KEY_OPTIMIZE_REF_OR_NULL));
3958
old->null_rejecting= (old->null_rejecting &&
3959
new_fields->null_rejecting);
3961
else if (old->eq_func && new_fields->eq_func &&
3962
((old->val->const_item() && old->val->is_null()) ||
3963
new_fields->val->is_null()))
3965
/* field = expression OR field IS NULL */
3966
old->level= and_level;
3967
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
3969
Remember the NOT NULL value unless the value does not depend
3972
if (!old->val->used_tables() && old->val->is_null())
3973
old->val= new_fields->val;
3974
/* The referred expression can be NULL: */
3975
old->null_rejecting= 0;
3980
We are comparing two different const. In this case we can't
3981
use a key-lookup on this so it's better to remove the value
3982
and let the range optimzier handle it
3984
if (old == --first_free) // If last item
3986
*old= *first_free; // Remove old value
3987
old--; // Retry this value
3992
/* Remove all not used items */
3993
for (KEY_FIELD *old=start ; old != first_free ;)
3995
if (old->level != and_level)
3996
{ // Not used in all levels
3997
if (old == --first_free)
3999
*old= *first_free; // Remove old value
4009
Add a possible key to array of possible keys if it's usable as a key
4011
@param key_fields Pointer to add key, if usable
4012
@param and_level And level, to be stored in KEY_FIELD
4013
@param cond Condition predicate
4014
@param field Field used in comparision
4015
@param eq_func True if we used =, <=> or IS NULL
4016
@param value Value used for comparison with field
4017
@param usable_tables Tables which can be used for key optimization
4018
@param sargables IN/OUT Array of found sargable candidates
4021
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
4022
table, we store this to be able to do not exists optimization later.
4025
*key_fields is incremented if we stored a key in the array
4029
add_key_field(KEY_FIELD **key_fields,uint32_t and_level, Item_func *cond,
4030
Field *field, bool eq_func, Item **value, uint32_t num_values,
4031
table_map usable_tables, SARGABLE_PARAM **sargables)
4033
uint32_t exists_optimize= 0;
4034
if (!(field->flags & PART_KEY_FLAG))
4036
// Don't remove column IS NULL on a LEFT JOIN table
4037
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4038
!field->table->maybe_null || field->null_ptr)
4039
return; // Not a key. Skip it
4040
exists_optimize= KEY_OPTIMIZE_EXISTS;
4041
assert(num_values == 1);
4045
table_map used_tables=0;
4047
for (uint32_t i=0; i<num_values; i++)
4049
used_tables|=(value[i])->used_tables();
4050
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
4055
if (!(usable_tables & field->table->map))
4057
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4058
!field->table->maybe_null || field->null_ptr)
4059
return; // Can't use left join optimize
4060
exists_optimize= KEY_OPTIMIZE_EXISTS;
4064
JOIN_TAB *stat=field->table->reginfo.join_tab;
4065
key_map possible_keys=field->key_start;
4066
possible_keys.intersect(field->table->keys_in_use_for_query);
4067
stat[0].keys.merge(possible_keys); // Add possible keys
4070
Save the following cases:
4072
Field LIKE constant where constant doesn't start with a wildcard
4073
Field = field2 where field2 is in a different table
4080
stat[0].key_dependent|=used_tables;
4083
for (uint32_t i=0; i<num_values; i++)
4085
if (!(is_const&= value[i]->const_item()))
4089
stat[0].const_keys.merge(possible_keys);
4093
Save info to be able check whether this predicate can be
4094
considered as sargable for range analisis after reading const tables.
4095
We do not save info about equalities as update_const_equal_items
4096
will take care of updating info on keys from sargable equalities.
4099
(*sargables)->field= field;
4100
(*sargables)->arg_value= value;
4101
(*sargables)->num_values= num_values;
4104
We can't always use indexes when comparing a string index to a
4105
number. cmp_type() is checked to allow compare of dates to numbers.
4106
eq_func is NEVER true when num_values > 1
4111
Additional optimization: if we're processing
4112
"t.key BETWEEN c1 AND c1" then proceed as if we were processing
4114
TODO: This is a very limited fix. A more generic fix is possible.
4115
There are 2 options:
4116
A) Make equality propagation code be able to handle BETWEEN
4117
(including cases like t1.key BETWEEN t2.key AND t3.key)
4118
B) Make range optimizer to infer additional "t.key = c" equalities
4119
and use them in equality propagation process (see details in
4122
if ((cond->functype() != Item_func::BETWEEN) ||
4123
((Item_func_between*) cond)->negated ||
4124
!value[0]->eq(value[1], field->binary()))
4129
if (field->result_type() == STRING_RESULT)
4131
if ((*value)->result_type() != STRING_RESULT)
4133
if (field->cmp_type() != (*value)->result_type())
4139
We can't use indexes if the effective collation
4140
of the operation differ from the field collation.
4142
if (field->cmp_type() == STRING_RESULT &&
4143
((Field_str*)field)->charset() != cond->compare_collation())
4150
For the moment eq_func is always true. This slot is reserved for future
4151
extensions where we want to remembers other things than just eq comparisons
4154
/* Store possible eq field */
4155
(*key_fields)->field= field;
4156
(*key_fields)->eq_func= eq_func;
4157
(*key_fields)->val= *value;
4158
(*key_fields)->level= and_level;
4159
(*key_fields)->optimize= exists_optimize;
4161
If the condition has form "tbl.keypart = othertbl.field" and
4162
othertbl.field can be NULL, there will be no matches if othertbl.field
4164
We use null_rejecting in add_not_null_conds() to add
4165
'othertbl.field IS NOT NULL' to tab->select_cond.
4167
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
4168
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
4169
((*value)->type() == Item::FIELD_ITEM) &&
4170
((Item_field*)*value)->field->maybe_null());
4171
(*key_fields)->cond_guard= NULL;
4172
(*key_fields)->sj_pred_no= (cond->name >= subq_sj_cond_name &&
4173
cond->name < subq_sj_cond_name + 64)?
4174
cond->name - subq_sj_cond_name: UINT_MAX;
4179
Add possible keys to array of possible keys originated from a simple
4182
@param key_fields Pointer to add key, if usable
4183
@param and_level And level, to be stored in KEY_FIELD
4184
@param cond Condition predicate
4185
@param field Field used in comparision
4186
@param eq_func True if we used =, <=> or IS NULL
4187
@param value Value used for comparison with field
4188
Is NULL for BETWEEN and IN
4189
@param usable_tables Tables which can be used for key optimization
4190
@param sargables IN/OUT Array of found sargable candidates
4193
If field items f1 and f2 belong to the same multiple equality and
4194
a key is added for f1, the the same key is added for f2.
4197
*key_fields is incremented if we stored a key in the array
4201
add_key_equal_fields(KEY_FIELD **key_fields, uint32_t and_level,
4202
Item_func *cond, Item_field *field_item,
4203
bool eq_func, Item **val,
4204
uint32_t num_values, table_map usable_tables,
4205
SARGABLE_PARAM **sargables)
4207
Field *field= field_item->field;
4208
add_key_field(key_fields, and_level, cond, field,
4209
eq_func, val, num_values, usable_tables, sargables);
4210
Item_equal *item_equal= field_item->item_equal;
4214
Add to the set of possible key values every substitution of
4215
the field for an equal field included into item_equal
4217
Item_equal_iterator it(*item_equal);
4219
while ((item= it++))
4221
if (!field->eq(item->field))
4223
add_key_field(key_fields, and_level, cond, item->field,
4224
eq_func, val, num_values, usable_tables,
4232
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint32_t *and_level,
4233
COND *cond, table_map usable_tables,
4234
SARGABLE_PARAM **sargables)
4236
if (cond->type() == Item_func::COND_ITEM)
4238
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
4239
KEY_FIELD *org_key_fields= *key_fields;
4241
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
4245
add_key_fields(join, key_fields, and_level, item, usable_tables,
4247
for (; org_key_fields != *key_fields ; org_key_fields++)
4248
org_key_fields->level= *and_level;
4253
add_key_fields(join, key_fields, and_level, li++, usable_tables,
4258
KEY_FIELD *start_key_fields= *key_fields;
4260
add_key_fields(join, key_fields, and_level, item, usable_tables,
4262
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
4263
*key_fields,++(*and_level));
4270
Subquery optimization: Conditions that are pushed down into subqueries
4271
are wrapped into Item_func_trig_cond. We process the wrapped condition
4272
but need to set cond_guard for KEYUSE elements generated from it.
4275
if (cond->type() == Item::FUNC_ITEM &&
4276
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
4278
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
4279
if (!join->group_list && !join->order &&
4281
join->unit->item->substype() == Item_subselect::IN_SUBS &&
4282
!join->unit->is_union())
4284
KEY_FIELD *save= *key_fields;
4285
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
4287
// Indicate that this ref access candidate is for subquery lookup:
4288
for (; save != *key_fields; save++)
4289
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
4295
/* If item is of type 'field op field/constant' add it to key_fields */
4296
if (cond->type() != Item::FUNC_ITEM)
4298
Item_func *cond_func= (Item_func*) cond;
4299
switch (cond_func->select_optimize()) {
4300
case Item_func::OPTIMIZE_NONE:
4302
case Item_func::OPTIMIZE_KEY:
4306
if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
4307
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4309
values= cond_func->arguments()+1;
4310
if (cond_func->functype() == Item_func::NE_FUNC &&
4311
cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4312
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4314
assert(cond_func->functype() != Item_func::IN_FUNC ||
4315
cond_func->argument_count() != 2);
4316
add_key_equal_fields(key_fields, *and_level, cond_func,
4317
(Item_field*) (cond_func->key_item()->real_item()),
4319
cond_func->argument_count()-1,
4320
usable_tables, sargables);
4322
if (cond_func->functype() == Item_func::BETWEEN)
4324
values= cond_func->arguments();
4325
for (uint32_t i= 1 ; i < cond_func->argument_count() ; i++)
4327
Item_field *field_item;
4328
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
4330
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
4332
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
4333
add_key_equal_fields(key_fields, *and_level, cond_func,
4334
field_item, 0, values, 1, usable_tables,
4341
case Item_func::OPTIMIZE_OP:
4343
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
4344
cond_func->functype() == Item_func::EQUAL_FUNC);
4346
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4347
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4349
add_key_equal_fields(key_fields, *and_level, cond_func,
4350
(Item_field*) (cond_func->arguments()[0])->real_item(),
4352
cond_func->arguments()+1, 1, usable_tables,
4355
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4356
cond_func->functype() != Item_func::LIKE_FUNC &&
4357
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
4359
add_key_equal_fields(key_fields, *and_level, cond_func,
4360
(Item_field*) (cond_func->arguments()[1])->real_item(),
4362
cond_func->arguments(),1,usable_tables,
4367
case Item_func::OPTIMIZE_NULL:
4368
/* column_name IS [NOT] NULL */
4369
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4370
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4372
Item *tmp=new Item_null;
4373
if (unlikely(!tmp)) // Should never be true
4375
add_key_equal_fields(key_fields, *and_level, cond_func,
4376
(Item_field*) (cond_func->arguments()[0])->real_item(),
4377
cond_func->functype() == Item_func::ISNULL_FUNC,
4378
&tmp, 1, usable_tables, sargables);
4381
case Item_func::OPTIMIZE_EQUAL:
4382
Item_equal *item_equal= (Item_equal *) cond;
4383
Item *const_item= item_equal->get_const();
4384
Item_equal_iterator it(*item_equal);
4389
For each field field1 from item_equal consider the equality
4390
field1=const_item as a condition allowing an index access of the table
4391
with field1 by the keys value of field1.
4393
while ((item= it++))
4395
add_key_field(key_fields, *and_level, cond_func, item->field,
4396
true, &const_item, 1, usable_tables, sargables);
4402
Consider all pairs of different fields included into item_equal.
4403
For each of them (field1, field1) consider the equality
4404
field1=field2 as a condition allowing an index access of the table
4405
with field1 by the keys value of field2.
4407
Item_equal_iterator fi(*item_equal);
4408
while ((item= fi++))
4410
Field *field= item->field;
4411
while ((item= it++))
4413
if (!field->eq(item->field))
4415
add_key_field(key_fields, *and_level, cond_func, field,
4416
true, (Item **) &item, 1, usable_tables,
495
4428
Add all keys with uses 'field' for some keypart.
497
4430
If field->and_level != and_level then only mark key_part as const_part.
499
uint32_t max_part_bit(key_part_map bits)
4434
max_part_bit(key_part_map bits)
502
4437
for (found=0; bits & 1 ; found++,bits>>=1) ;
506
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)
4442
add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
4444
Field *field=key_field->field;
4445
Table *form= field->table;
4448
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
4450
for (uint32_t key= 0 ; key < form->sizeKeys() ; key++)
4452
if (!(form->keys_in_use_for_query.is_set(key)))
4455
uint32_t key_parts= (uint) form->key_info[key].key_parts;
4456
for (uint32_t part=0 ; part < key_parts ; part++)
4458
if (field->eq(form->key_info[key].key_part[part].field))
4460
keyuse.table= field->table;
4461
keyuse.val = key_field->val;
4463
keyuse.keypart=part;
4464
keyuse.keypart_map= (key_part_map) 1 << part;
4465
keyuse.used_tables=key_field->val->used_tables();
4466
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
4467
keyuse.null_rejecting= key_field->null_rejecting;
4468
keyuse.cond_guard= key_field->cond_guard;
4469
keyuse.sj_pred_no= key_field->sj_pred_no;
4470
insert_dynamic(keyuse_array,(unsigned char*) &keyuse);
4478
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()));
4481
if (a->table->tablenr != b->table->tablenr)
4482
return (int) (a->table->tablenr - b->table->tablenr);
4483
if (a->key != b->key)
4484
return (int) (a->key - b->key);
4485
if (a->keypart != b->keypart)
4486
return (int) (a->keypart - b->keypart);
515
4487
// Place const values before other ones
516
if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -
517
test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))
4488
if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
4489
test((b->used_tables & ~OUTER_REF_TABLE_BIT))))
519
4491
/* 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)));
4492
return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
4493
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
4498
Add to KEY_FIELD array all 'ref' access candidates within nested join.
4500
This function populates KEY_FIELD array with entries generated from the
4501
ON condition of the given nested join, and does the same for nested joins
4502
contained within this nested join.
4504
@param[in] nested_join_table Nested join pseudo-table to process
4505
@param[in,out] end End of the key field array
4506
@param[in,out] and_level And-level
4507
@param[in,out] sargables Array of found sargable candidates
4511
We can add accesses to the tables that are direct children of this nested
4512
join (1), and are not inner tables w.r.t their neighbours (2).
4514
Example for #1 (outer brackets pair denotes nested join this function is
4517
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
4521
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
4523
In examples 1-2 for condition cond, we can add 'ref' access candidates to
4527
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
4529
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
4532
static void add_key_fields_for_nj(JOIN *join, TableList *nested_join_table,
4533
KEY_FIELD **end, uint32_t *and_level,
4534
SARGABLE_PARAM **sargables)
4536
List_iterator<TableList> li(nested_join_table->nested_join->join_list);
4537
List_iterator<TableList> li2(nested_join_table->nested_join->join_list);
4538
bool have_another = false;
4539
table_map tables= 0;
4541
assert(nested_join_table->nested_join);
4543
while ((table= li++) || (have_another && (li=li2, have_another=false,
4546
if (table->nested_join)
4548
if (!table->on_expr)
4550
/* It's a semi-join nest. Walk into it as if it wasn't a nest */
4553
li= List_iterator<TableList>(table->nested_join->join_list);
4556
add_key_fields_for_nj(join, table, end, and_level, sargables);
4559
if (!table->on_expr)
4560
tables |= table->table->map;
4562
if (nested_join_table->on_expr)
4563
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
781
4827
/* Intersect the keys of all group fields. */
782
4828
cur_item= indexed_fields_it++;
783
possible_keys|= cur_item->field->part_of_key;
4829
possible_keys.merge(cur_item->field->part_of_key);
784
4830
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
4832
possible_keys.intersect(cur_item->field->part_of_key);
4835
if (!possible_keys.is_clear_all())
4836
join_tab->const_keys.merge(possible_keys);
4840
/*****************************************************************************
4841
Go through all combinations of not marked tables and find the one
4842
which uses least records
4843
*****************************************************************************/
4845
/** Save const tables first as used tables. */
4848
set_position(JOIN *join,uint32_t idx,JOIN_TAB *table,KEYUSE *key)
4850
join->positions[idx].table= table;
4851
join->positions[idx].key=key;
4852
join->positions[idx].records_read=1.0; /* This is a const table */
4853
join->positions[idx].ref_depend_map= 0;
4855
/* Move the const table as down as possible in best_ref */
4856
JOIN_TAB **pos=join->best_ref+idx+1;
4857
JOIN_TAB *next=join->best_ref[idx];
4858
for (;next != table ; pos++)
4860
JOIN_TAB *tmp=pos[0];
4864
join->best_ref[idx]=table;
4869
Given a semi-join nest, find out which of the IN-equalities are bound
4872
get_bound_sj_equalities()
4873
sj_nest Semi-join nest
4874
remaining_tables Tables that are not yet bound
4877
Given a semi-join nest, find out which of the IN-equalities have their
4878
left part expression bound (i.e. the said expression doesn't refer to
4879
any of remaining_tables and can be evaluated).
4882
Bitmap of bound IN-equalities.
4885
uint64_t get_bound_sj_equalities(TableList *sj_nest,
4886
table_map remaining_tables)
4888
List_iterator<Item> li(sj_nest->nested_join->sj_outer_expr_list);
4892
while ((item= li++))
4895
Q: should this take into account equality propagation and how?
4896
A: If e->outer_side is an Item_field, walk over the equality
4897
class and see if there is an element that is bound?
4898
(this is an optional feature)
4900
if (!(item->used_tables() & remaining_tables))
4910
Find the best access path for an extension of a partial execution
4911
plan and add this path to the plan.
4913
The function finds the best access path to table 's' from the passed
4914
partial plan where an access path is the general term for any means to
4915
access the data in 's'. An access path may use either an index or a scan,
4916
whichever is cheaper. The input partial plan is passed via the array
4917
'join->positions' of length 'idx'. The chosen access method for 's' and its
4918
cost are stored in 'join->positions[idx]'.
4920
@param join pointer to the structure providing all context info
4922
@param s the table to be joined by the function
4923
@param session thread for the connection that submitted the query
4924
@param remaining_tables set of tables not included into the partial plan yet
4925
@param idx the length of the partial plan
4926
@param record_count estimate for the number of records returned by the
4928
@param read_time the cost of the partial plan
4935
best_access_path(JOIN *join,
4938
table_map remaining_tables,
4940
double record_count,
4943
KEYUSE *best_key= 0;
4944
uint32_t best_max_key_part= 0;
4945
bool found_constraint= 0;
4946
double best= DBL_MAX;
4947
double best_time= DBL_MAX;
4948
double records= DBL_MAX;
4949
table_map best_ref_depends_map= 0;
4952
uint32_t best_is_sj_inside_out= 0;
4955
{ /* Use key if possible */
4956
Table *table= s->table;
4957
KEYUSE *keyuse,*start_key=0;
4958
double best_records= DBL_MAX;
4959
uint32_t max_key_part=0;
4960
uint64_t bound_sj_equalities= 0;
4961
bool try_sj_inside_out= false;
4963
Discover the bound equalites. We need to do this, if
4964
1. The next table is an SJ-inner table, and
4965
2. It is the first table from that semijoin, and
4966
3. We're not within a semi-join range (i.e. all semi-joins either have
4967
all or none of their tables in join_table_map), except
4968
s->emb_sj_nest (which we've just entered).
4969
3. All correlation references from this sj-nest are bound
4971
if (s->emb_sj_nest && // (1)
4972
s->emb_sj_nest->sj_in_exprs < 64 &&
4973
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
4974
s->emb_sj_nest->sj_inner_tables) && // (2)
4975
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
4976
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
4978
/* This table is an InsideOut scan candidate */
4979
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
4981
try_sj_inside_out= true;
4984
/* Test how we can use keys */
4985
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
4986
for (keyuse=s->keyuse ; keyuse->table == table ;)
4988
key_part_map found_part= 0;
4989
table_map found_ref= 0;
4990
uint32_t key= keyuse->key;
4991
KEY *keyinfo= table->key_info+key;
4992
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
4993
key_part_map const_part= 0;
4994
/* The or-null keypart in ref-or-null access: */
4995
key_part_map ref_or_null_part= 0;
4997
/* Calculate how many key segments of the current key we can use */
4999
uint64_t handled_sj_equalities=0;
5000
key_part_map sj_insideout_map= 0;
5002
do /* For each keypart */
5004
uint32_t keypart= keyuse->keypart;
5005
table_map best_part_found_ref= 0;
5006
double best_prev_record_reads= DBL_MAX;
5008
do /* For each way to access the keypart */
5012
if 1. expression doesn't refer to forward tables
5013
2. we won't get two ref-or-null's
5015
if (!(remaining_tables & keyuse->used_tables) &&
5016
!(ref_or_null_part && (keyuse->optimize &
5017
KEY_OPTIMIZE_REF_OR_NULL)))
5019
found_part|= keyuse->keypart_map;
5020
if (!(keyuse->used_tables & ~join->const_table_map))
5021
const_part|= keyuse->keypart_map;
5023
double tmp2= prev_record_reads(join, idx, (found_ref |
5024
keyuse->used_tables));
5025
if (tmp2 < best_prev_record_reads)
5027
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
5028
best_prev_record_reads= tmp2;
5030
if (rec > keyuse->ref_table_rows)
5031
rec= keyuse->ref_table_rows;
5033
If there is one 'key_column IS NULL' expression, we can
5034
use this ref_or_null optimisation of this field
5036
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
5037
ref_or_null_part |= keyuse->keypart_map;
5040
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
5042
if (!(remaining_tables & keyuse->used_tables))
5043
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
5046
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
5047
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
5052
} while (keyuse->table == table && keyuse->key == key &&
5053
keyuse->keypart == keypart);
5054
found_ref|= best_part_found_ref;
5055
} while (keyuse->table == table && keyuse->key == key);
5058
Assume that that each key matches a proportional part of table.
5060
if (!found_part && !handled_sj_equalities)
5061
continue; // Nothing usable found
5063
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
5064
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
5066
bool sj_inside_out_scan= false;
5068
found_constraint= 1;
5070
Check if InsideOut scan is applicable:
5071
1. All IN-equalities are either "bound" or "handled"
5072
2. Index keyparts are
5075
if (try_sj_inside_out &&
5076
table->covering_keys.is_set(key) &&
5077
(handled_sj_equalities | bound_sj_equalities) == // (1)
5078
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
5080
uint32_t n_fixed_parts= max_part_bit(found_part);
5081
if (n_fixed_parts != keyinfo->key_parts &&
5082
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
5083
PREV_BITS(uint, keyinfo->key_parts))
5086
Not all parts are fixed. Produce bitmap of remaining bits and
5087
check if all of them are covered.
5089
sj_inside_out_scan= true;
5093
It's a confluent ref scan.
5095
That is, all found KEYUSE elements refer to IN-equalities,
5096
and there is really no ref access because there is no
5097
t.keypart0 = {bound expression}
5099
Calculate the cost of complete loose index scan.
5101
records= (double)s->table->file->stats.records;
5103
/* The cost is entire index scan cost (divided by 2) */
5104
best_time= s->table->file->index_only_read_time(key, records);
5106
/* Now figure how many different keys we will get */
5108
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
5109
records= records / rpc;
5116
Check if we found full key
5118
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
5121
max_key_part= UINT32_MAX;
5122
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
5124
tmp = prev_record_reads(join, idx, found_ref);
5130
{ /* We found a const key */
5132
ReuseRangeEstimateForRef-1:
5133
We get here if we've found a ref(const) (c_i are constants):
5134
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
5136
If range optimizer was able to construct a "range"
5137
access on this index, then its condition "quick_cond" was
5138
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
5139
from the range optimizer.
5141
Proof of (*): By properties of range and ref optimizers
5142
quick_cond will be equal or tighther than ref_const_cond.
5143
ref_const_cond already covers "smallest" possible interval -
5144
a singlepoint interval over all keyparts. Therefore,
5145
quick_cond is equivalent to ref_const_cond (if it was an
5146
empty interval we wouldn't have got here).
5148
if (table->quick_keys.is_set(key))
5149
records= (double) table->quick_rows[key];
5152
/* quick_range couldn't use key! */
5153
records= (double) s->records/rec;
5158
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
5159
{ /* Prefer longer keys */
5161
((double) s->records / (double) rec *
5163
((double) (table->s->max_key_length-keyinfo->key_length) /
5164
(double) table->s->max_key_length)));
5166
records=2.0; /* Can't be as good as a unique */
5169
ReuseRangeEstimateForRef-2: We get here if we could not reuse
5170
E(#rows) from range optimizer. Make another try:
5172
If range optimizer produced E(#rows) for a prefix of the ref
5173
access we're considering, and that E(#rows) is lower then our
5174
current estimate, make an adjustment. The criteria of when we
5175
can make an adjustment is a special case of the criteria used
5176
in ReuseRangeEstimateForRef-3.
5178
if (table->quick_keys.is_set(key) &&
5179
const_part & (1 << table->quick_key_parts[key]) &&
5180
table->quick_n_ranges[key] == 1 &&
5181
records > (double) table->quick_rows[key])
5183
records= (double) table->quick_rows[key];
5186
/* Limit the number of matched rows */
5188
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5189
if (table->covering_keys.is_set(key))
5191
/* we can use only index tree */
5192
tmp= record_count * table->file->index_only_read_time(key, tmp);
5195
tmp= record_count*cmin(tmp,s->worst_seeks);
5201
Use as much key-parts as possible and a uniq key is better
5202
than a not unique key
5203
Set tmp to (previous record count) * (records / combination)
5205
if ((found_part & 1) &&
5206
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
5207
found_part == PREV_BITS(uint,keyinfo->key_parts)))
5209
max_key_part= max_part_bit(found_part);
5211
ReuseRangeEstimateForRef-3:
5212
We're now considering a ref[or_null] access via
5213
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
5214
(same-as-above but with one cond replaced
5215
with "t.keypart_i IS NULL")] (**)
5217
Try re-using E(#rows) from "range" optimizer:
5218
We can do so if "range" optimizer used the same intervals as
5219
in (**). The intervals used by range optimizer may be not
5220
available at this point (as "range" access might have choosen to
5221
create quick select over another index), so we can't compare
5222
them to (**). We'll make indirect judgements instead.
5223
The sufficient conditions for re-use are:
5224
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
5225
this is not satisfied we have no way to know which ranges
5226
will be actually scanned by 'ref' until we execute the
5228
(C2) max #key parts in 'range' access == K == max_key_part (this
5229
is apparently a necessary requirement)
5231
We also have a property that "range optimizer produces equal or
5232
tighter set of scan intervals than ref(const) optimizer". Each
5233
of the intervals in (**) are "tightest possible" intervals when
5234
one limits itself to using keyparts 1..K (which we do in #2).
5235
From here it follows that range access used either one, or
5236
both of the (I1) and (I2) intervals:
5238
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
5239
(same-as-above but with one cond replaced
5240
with "t.keypart_i IS NULL") (I2)
5242
The remaining part is to exclude the situation where range
5243
optimizer used one interval while we're considering
5244
ref-or-null and looking for estimate for two intervals. This
5245
is done by last limitation:
5247
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
5249
if (table->quick_keys.is_set(key) && !found_ref && //(C1)
5250
table->quick_key_parts[key] == max_key_part && //(C2)
5251
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
5253
tmp= records= (double) table->quick_rows[key];
5257
/* Check if we have statistic about the distribution */
5258
if ((records= keyinfo->rec_per_key[max_key_part-1]))
5261
Fix for the case where the index statistics is too
5263
(1) We're considering ref(const) and there is quick select
5265
(2) and that quick select uses more keyparts (i.e. it will
5266
scan equal/smaller interval then this ref(const))
5267
(3) and E(#rows) for quick select is higher then our
5270
We'll use E(#rows) from quick select.
5272
Q: Why do we choose to use 'ref'? Won't quick select be
5273
cheaper in some cases ?
5274
TODO: figure this out and adjust the plan choice if needed.
5276
if (!found_ref && table->quick_keys.is_set(key) && // (1)
5277
table->quick_key_parts[key] > max_key_part && // (2)
5278
records < (double)table->quick_rows[key]) // (3)
5279
records= (double)table->quick_rows[key];
5286
Assume that the first key part matches 1% of the file
5287
and that the whole key matches 10 (duplicates) or 1
5289
Assume also that more key matches proportionally more
5291
This gives the formula:
5292
records = (x * (b-a) + a*c-b)/(c-1)
5294
b = records matched by whole key
5295
a = records matched by first key part (1% of all records?)
5296
c = number of key parts in key
5297
x = used key parts (1 <= x <= c)
5300
if (!(rec_per_key=(double)
5301
keyinfo->rec_per_key[keyinfo->key_parts-1]))
5302
rec_per_key=(double) s->records/rec+1;
5306
else if (rec_per_key/(double) s->records >= 0.01)
5310
double a=s->records*0.01;
5311
if (keyinfo->key_parts > 1)
5312
tmp= (max_key_part * (rec_per_key - a) +
5313
a*keyinfo->key_parts - rec_per_key)/
5314
(keyinfo->key_parts-1);
5317
set_if_bigger(tmp,1.0);
5319
records = (uint32_t) tmp;
5322
if (ref_or_null_part)
5324
/* We need to do two key searches to find key */
5330
ReuseRangeEstimateForRef-4: We get here if we could not reuse
5331
E(#rows) from range optimizer. Make another try:
5333
If range optimizer produced E(#rows) for a prefix of the ref
5334
access we're considering, and that E(#rows) is lower then our
5335
current estimate, make the adjustment.
5337
The decision whether we can re-use the estimate from the range
5338
optimizer is the same as in ReuseRangeEstimateForRef-3,
5339
applied to first table->quick_key_parts[key] key parts.
5341
if (table->quick_keys.is_set(key) &&
5342
table->quick_key_parts[key] <= max_key_part &&
5343
const_part & (1 << table->quick_key_parts[key]) &&
5344
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
5345
const_part) ? 1 : 0) &&
5346
records > (double) table->quick_rows[key])
5348
tmp= records= (double) table->quick_rows[key];
5352
/* Limit the number of matched rows */
5353
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5354
if (table->covering_keys.is_set(key))
5356
/* we can use only index tree */
5357
tmp= record_count * table->file->index_only_read_time(key, tmp);
5360
tmp= record_count * cmin(tmp,s->worst_seeks);
5363
tmp= best_time; // Do nothing
5366
if (sj_inside_out_scan && !start_key)
5374
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
5376
best_time= tmp + records/(double) TIME_FOR_COMPARE;
5378
best_records= records;
5379
best_key= start_key;
5380
best_max_key_part= max_key_part;
5381
best_ref_depends_map= found_ref;
5382
best_is_sj_inside_out= sj_inside_out_scan;
5385
records= best_records;
5389
Don't test table scan if it can't be better.
5390
Prefer key lookup if we would use the same key for scanning.
5392
Don't do a table scan on InnoDB tables, if we can read the used
5393
parts of the row from any of the used index.
5394
This is because table scans uses index and we would not win
5395
anything by using a table scan.
5397
A word for word translation of the below if-statement in sergefp's
5398
understanding: we check if we should use table scan if:
5399
(1) The found 'ref' access produces more records than a table scan
5400
(or index scan, or quick select), or 'ref' is more expensive than
5402
(2) This doesn't hold: the best way to perform table scan is to to perform
5403
'range' access using index IDX, and the best way to perform 'ref'
5404
access is to use the same index IDX, with the same or more key parts.
5405
(note: it is not clear how this rule is/should be extended to
5406
index_merge quick selects)
5407
(3) See above note about InnoDB.
5408
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
5409
path, but there is no quick select)
5410
If the condition in the above brackets holds, then the only possible
5411
"table scan" access method is ALL/index (there is no quick select).
5412
Since we have a 'ref' access path, and FORCE INDEX instructs us to
5413
choose it over ALL/index, there is no need to consider a full table
5416
if ((records >= s->found_records || best > s->read_time) && // (1)
5417
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
5418
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
5419
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
5420
! s->table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
5421
!(s->table->force_index && best_key && !s->quick)) // (4)
5422
{ // Check full join
5423
ha_rows rnd_records= s->found_records;
5425
If there is a filtering condition on the table (i.e. ref analyzer found
5426
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
5427
preceding this table in the join order we're now considering), then
5428
assume that 25% of the rows will be filtered out by this condition.
5430
This heuristic is supposed to force tables used in exprZ to be before
5431
this table in join order.
5433
if (found_constraint)
5434
rnd_records-= rnd_records/4;
5437
If applicable, get a more accurate estimate. Don't use the two
5440
if (s->table->quick_condition_rows != s->found_records)
5441
rnd_records= s->table->quick_condition_rows;
5444
Range optimizer never proposes a RANGE if it isn't better
5445
than FULL: so if RANGE is present, it's always preferred to FULL.
5446
Here we estimate its cost.
5452
- read record range through 'quick'
5453
- skip rows which does not satisfy WHERE constraints
5455
We take into account possible use of join cache for ALL/index
5456
access (see first else-branch below), but we don't take it into
5457
account here for range/index_merge access. Find out why this is so.
5460
(s->quick->read_time +
5461
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
5465
/* Estimate cost of reading table. */
5466
tmp= s->table->file->scan_time();
5467
if (s->table->map & join->outer_join) // Can't use join cache
5470
For each record we have to:
5471
- read the whole table record
5472
- skip rows which does not satisfy join condition
5476
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
5480
/* We read the table as many times as join buffer becomes full. */
5481
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
5483
(double) session->variables.join_buff_size));
5485
We don't make full cartesian product between rows in the scanned
5486
table and existing records because we skip all rows from the
5487
scanned table, which does not satisfy join condition when
5488
we read the table (see flush_cached_records for details). Here we
5489
take into account cost to read and skip these records.
5491
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
5496
We estimate the cost of evaluating WHERE clause for found records
5497
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
5498
tmp give us total cost of using Table SCAN
5500
if (best == DBL_MAX ||
5501
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
5502
best + record_count/(double) TIME_FOR_COMPARE*records))
5505
If the table has a range (s->quick is set) make_join_select()
5506
will ensure that this will be used
5509
records= rows2double(rnd_records);
5511
/* range/index_merge/ALL/index access method are "independent", so: */
5512
best_ref_depends_map= 0;
5513
best_is_sj_inside_out= false;
5517
/* Update the cost information for the current partial plan */
5518
join->positions[idx].records_read= records;
5519
join->positions[idx].read_time= best;
5520
join->positions[idx].key= best_key;
5521
join->positions[idx].table= s;
5522
join->positions[idx].ref_depend_map= best_ref_depends_map;
5523
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
5526
idx == join->const_tables &&
5527
s->table == join->sort_by_table &&
5528
join->unit->select_limit_cnt >= records)
5529
join->sort_by_table= (Table*) 1; // Must use temporary table
5536
Selects and invokes a search strategy for an optimal query plan.
5538
The function checks user-configurable parameters that control the search
5539
strategy for an optimal plan, selects the search method and then invokes
5540
it. Each specific optimization procedure stores the final optimal plan in
5541
the array 'join->best_positions', and the cost of the plan in
5544
@param join pointer to the structure providing all context info for
5546
@param join_tables set of the tables in the query
5549
'MAX_TABLES+2' denotes the old implementation of find_best before
5550
the greedy version. Will be removed when greedy_search is approved.
5559
choose_plan(JOIN *join, table_map join_tables)
5561
uint32_t search_depth= join->session->variables.optimizer_search_depth;
5562
uint32_t prune_level= join->session->variables.optimizer_prune_level;
5563
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
5565
join->cur_embedding_map= 0;
5566
reset_nj_counters(join->join_list);
5568
if (SELECT_STRAIGHT_JOIN option is set)
5569
reorder tables so dependent tables come after tables they depend
5570
on, otherwise keep tables in the order they were specified in the query
5572
Apply heuristic: pre-sort all access plans with respect to the number of
5575
my_qsort(join->best_ref + join->const_tables,
5576
join->tables - join->const_tables, sizeof(JOIN_TAB*),
5577
straight_join ? join_tab_cmp_straight : join_tab_cmp);
5578
join->cur_emb_sj_nests= 0;
5581
optimize_straight_join(join, join_tables);
5585
if (search_depth == MAX_TABLES+2)
5587
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
5588
the greedy version. Will be removed when greedy_search is approved.
5590
join->best_read= DBL_MAX;
5591
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
5596
if (search_depth == 0)
5597
/* Automatically determine a reasonable value for 'search_depth' */
5598
search_depth= determine_search_depth(join);
5599
if (greedy_search(join, join_tables, search_depth, prune_level))
5605
Store the cost of this query into a user variable
5606
Don't update last_query_cost for statements that are not "flat joins" :
5607
i.e. they have subqueries, unions or call stored procedures.
5608
TODO: calculate a correct cost for a query with subqueries and UNIONs.
5610
if (join->session->lex->is_single_level_stmt())
5611
join->session->status_var.last_query_cost= join->best_read;
5617
Compare two JOIN_TAB objects based on the number of accessed records.
5619
@param ptr1 pointer to first JOIN_TAB object
5620
@param ptr2 pointer to second JOIN_TAB object
800
5623
The order relation implemented by join_tab_cmp() is not transitive,
5677
Heuristic procedure to automatically guess a reasonable degree of
5678
exhaustiveness for the greedy search procedure.
5680
The procedure estimates the optimization time and selects a search depth
5681
big enough to result in a near-optimal QEP, that doesn't take too long to
5682
find. If the number of tables in the query exceeds some constant, then
5683
search_depth is set to this constant.
5685
@param join pointer to the structure providing all context info for
5689
This is an extremely simplistic implementation that serves as a stub for a
5690
more advanced analysis of the join. Ideally the search depth should be
5691
determined by learning from previous query optimizations, because it will
5692
depend on the CPU power (and other factors).
5695
this value should be determined dynamically, based on statistics:
5696
uint32_t max_tables_for_exhaustive_opt= 7;
5699
this value could be determined by some mapping of the form:
5700
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5703
A positive integer that specifies the search depth (and thus the
5704
exhaustiveness) of the depth-first search algorithm used by
5709
determine_search_depth(JOIN *join)
5711
uint32_t table_count= join->tables - join->const_tables;
5712
uint32_t search_depth;
5713
/* TODO: this value should be determined dynamically, based on statistics: */
5714
uint32_t max_tables_for_exhaustive_opt= 7;
5716
if (table_count <= max_tables_for_exhaustive_opt)
5717
search_depth= table_count+1; // use exhaustive for small number of tables
5720
TODO: this value could be determined by some mapping of the form:
5721
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5723
search_depth= max_tables_for_exhaustive_opt; // use greedy search
5725
return search_depth;
5730
Select the best ways to access the tables in a query without reordering them.
5732
Find the best access paths for each query table and compute their costs
5733
according to their order in the array 'join->best_ref' (thus without
5734
reordering the join tables). The function calls sequentially
5735
'best_access_path' for each table in the query to select the best table
5736
access method. The final optimal plan is stored in the array
5737
'join->best_positions', and the corresponding cost in 'join->best_read'.
5739
@param join pointer to the structure providing all context info for
5741
@param join_tables set of the tables in the query
5744
This function can be applied to:
5745
- queries with STRAIGHT_JOIN
5746
- internally to compute the cost of an arbitrary QEP
5748
Thus 'optimize_straight_join' can be used at any stage of the query
5749
optimization process to finalize a QEP as it is.
5753
optimize_straight_join(JOIN *join, table_map join_tables)
5756
uint32_t idx= join->const_tables;
5757
double record_count= 1.0;
5758
double read_time= 0.0;
5760
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
5762
/* Find the best access method from 's' to the current partial plan */
5763
advance_sj_state(join_tables, s);
5764
best_access_path(join, s, join->session, join_tables, idx,
5765
record_count, read_time);
5766
/* compute the cost of the new plan extended with 's' */
5767
record_count*= join->positions[idx].records_read;
5768
read_time+= join->positions[idx].read_time;
5769
join_tables&= ~(s->table->map);
5773
read_time+= record_count / (double) TIME_FOR_COMPARE;
5774
if (join->sort_by_table &&
5775
join->sort_by_table != join->positions[join->const_tables].table->table)
5776
read_time+= record_count; // We have to make a temp table
5777
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
5778
join->best_read= read_time;
5783
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
5785
The search procedure uses a hybrid greedy/exhaustive search with controlled
5786
exhaustiveness. The search is performed in N = card(remaining_tables)
5787
steps. Each step evaluates how promising is each of the unoptimized tables,
5788
selects the most promising table, and extends the current partial QEP with
5789
that table. Currenly the most 'promising' table is the one with least
5790
expensive extension.\
5792
There are two extreme cases:
5793
-# When (card(remaining_tables) < search_depth), the estimate finds the
5794
best complete continuation of the partial QEP. This continuation can be
5795
used directly as a result of the search.
5796
-# When (search_depth == 1) the 'best_extension_by_limited_search'
5797
consideres the extension of the current QEP with each of the remaining
5800
All other cases are in-between these two extremes. Thus the parameter
5801
'search_depth' controlls the exhaustiveness of the search. The higher the
5802
value, the longer the optimizaton time and possibly the better the
5803
resulting plan. The lower the value, the fewer alternative plans are
5804
estimated, but the more likely to get a bad QEP.
5806
All intermediate and final results of the procedure are stored in 'join':
5807
- join->positions : modified for every partial QEP that is explored
5808
- join->best_positions: modified for the current best complete QEP
5809
- join->best_read : modified for the current best complete QEP
5810
- join->best_ref : might be partially reordered
5812
The final optimal plan is stored in 'join->best_positions', and its
5813
corresponding cost in 'join->best_read'.
5816
The following pseudocode describes the algorithm of 'greedy_search':
5819
procedure greedy_search
5820
input: remaining_tables
5825
(t, a) = best_extension(pplan, remaining_tables);
5826
pplan = concat(pplan, (t, a));
5827
remaining_tables = remaining_tables - t;
5828
} while (remaining_tables != {})
5833
where 'best_extension' is a placeholder for a procedure that selects the
5834
most "promising" of all tables in 'remaining_tables'.
5835
Currently this estimate is performed by calling
5836
'best_extension_by_limited_search' to evaluate all extensions of the
5837
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
5838
mainly depends on that of 'best_extension_by_limited_search'.
5841
If 'best_extension()' == 'best_extension_by_limited_search()', then the
5842
worst-case complexity of this algorithm is <=
5843
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
5844
complexity of greedy_search is O(N!).
5847
In the future, 'greedy_search' might be extended to support other
5848
implementations of 'best_extension', e.g. some simpler quadratic procedure.
5850
@param join pointer to the structure providing all context info
5852
@param remaining_tables set of tables not included into the partial plan yet
5853
@param search_depth controlls the exhaustiveness of the search
5854
@param prune_level the pruning heuristics that should be applied during
5864
greedy_search(JOIN *join,
5865
table_map remaining_tables,
5866
uint32_t search_depth,
5867
uint32_t prune_level)
5869
double record_count= 1.0;
5870
double read_time= 0.0;
5871
uint32_t idx= join->const_tables; // index into 'join->best_ref'
5873
uint32_t size_remain; // cardinality of remaining_tables
5875
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
5877
/* number of tables that remain to be optimized */
5878
size_remain= my_count_bits(remaining_tables);
5881
/* Find the extension of the current QEP with the lowest cost */
5882
join->best_read= DBL_MAX;
5883
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
5884
read_time, search_depth, prune_level))
5887
if (size_remain <= search_depth)
5890
'join->best_positions' contains a complete optimal extension of the
5891
current partial QEP.
5896
/* select the first table in the optimal extension as most promising */
5897
best_pos= join->best_positions[idx];
5898
best_table= best_pos.table;
5900
Each subsequent loop of 'best_extension_by_limited_search' uses
5901
'join->positions' for cost estimates, therefore we have to update its
5904
join->positions[idx]= best_pos;
5906
/* find the position of 'best_table' in 'join->best_ref' */
5908
JOIN_TAB *pos= join->best_ref[best_idx];
5909
while (pos && best_table != pos)
5910
pos= join->best_ref[++best_idx];
5911
assert((pos != NULL)); // should always find 'best_table'
5912
/* move 'best_table' at the first free position in the array of joins */
5913
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
5915
/* compute the cost of the new plan extended with 'best_table' */
5916
record_count*= join->positions[idx].records_read;
5917
read_time+= join->positions[idx].read_time;
5919
remaining_tables&= ~(best_table->table->map);
5927
Find a good, possibly optimal, query execution plan (QEP) by a possibly
5930
The procedure searches for the optimal ordering of the query tables in set
5931
'remaining_tables' of size N, and the corresponding optimal access paths to
5932
each table. The choice of a table order and an access path for each table
5933
constitutes a query execution plan (QEP) that fully specifies how to
5936
The maximal size of the found plan is controlled by the parameter
5937
'search_depth'. When search_depth == N, the resulting plan is complete and
5938
can be used directly as a QEP. If search_depth < N, the found plan consists
5939
of only some of the query tables. Such "partial" optimal plans are useful
5940
only as input to query optimization procedures, and cannot be used directly
5943
The algorithm begins with an empty partial plan stored in 'join->positions'
5944
and a set of N tables - 'remaining_tables'. Each step of the algorithm
5945
evaluates the cost of the partial plan extended by all access plans for
5946
each of the relations in 'remaining_tables', expands the current partial
5947
plan with the access plan that results in lowest cost of the expanded
5948
partial plan, and removes the corresponding relation from
5949
'remaining_tables'. The algorithm continues until it either constructs a
5950
complete optimal plan, or constructs an optimal plartial plan with size =
5953
The final optimal plan is stored in 'join->best_positions'. The
5954
corresponding cost of the optimal plan is in 'join->best_read'.
5957
The procedure uses a recursive depth-first search where the depth of the
5958
recursion (and thus the exhaustiveness of the search) is controlled by the
5959
parameter 'search_depth'.
5962
The pseudocode below describes the algorithm of
5963
'best_extension_by_limited_search'. The worst-case complexity of this
5964
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
5965
the complexity of greedy_search is O(N!).
5968
procedure best_extension_by_limited_search(
5969
pplan in, // in, partial plan of tables-joined-so-far
5970
pplan_cost, // in, cost of pplan
5971
remaining_tables, // in, set of tables not referenced in pplan
5972
best_plan_so_far, // in/out, best plan found so far
5973
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5974
search_depth) // in, maximum size of the plans being considered
5976
for each table T from remaining_tables
5978
// Calculate the cost of using table T as above
5979
cost = complex-series-of-calculations;
5981
// Add the cost to the cost so far.
5984
if (pplan_cost >= best_plan_so_far_cost)
5985
// pplan_cost already too great, stop search
5988
pplan= expand pplan by best_access_method;
5989
remaining_tables= remaining_tables - table T;
5990
if (remaining_tables is not an empty set
5994
best_extension_by_limited_search(pplan, pplan_cost,
5997
best_plan_so_far_cost,
6002
best_plan_so_far_cost= pplan_cost;
6003
best_plan_so_far= pplan;
6010
When 'best_extension_by_limited_search' is called for the first time,
6011
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
6012
The actual implementation provides a way to optionally use pruning
6013
heuristic (controlled by the parameter 'prune_level') to reduce the search
6014
space by skipping some partial plans.
6017
The parameter 'search_depth' provides control over the recursion
6018
depth, and thus the size of the resulting optimal plan.
6020
@param join pointer to the structure providing all context info
6022
@param remaining_tables set of tables not included into the partial plan yet
6023
@param idx length of the partial QEP in 'join->positions';
6024
since a depth-first search is used, also corresponds
6025
to the current depth of the search tree;
6026
also an index in the array 'join->best_ref';
6027
@param record_count estimate for the number of records returned by the
6029
@param read_time the cost of the best partial plan
6030
@param search_depth maximum depth of the recursion and thus size of the
6032
(0 < search_depth <= join->tables+1).
6033
@param prune_level pruning heuristics that should be applied during
6035
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
6044
best_extension_by_limited_search(JOIN *join,
6045
table_map remaining_tables,
6047
double record_count,
6049
uint32_t search_depth,
6050
uint32_t prune_level)
6052
Session *session= join->session;
6053
if (session->killed) // Abort
6057
'join' is a partial plan with lower cost than the best plan so far,
6058
so continue expanding it further with the tables in 'remaining_tables'.
6061
double best_record_count= DBL_MAX;
6062
double best_read_time= DBL_MAX;
6064
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
6066
table_map real_table_bit= s->table->map;
6067
if ((remaining_tables & real_table_bit) &&
6068
!(remaining_tables & s->dependent) &&
6069
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6071
double current_record_count, current_read_time;
6072
advance_sj_state(remaining_tables, s);
6075
psergey-insideout-todo:
6076
when best_access_path() detects it could do an InsideOut scan or
6077
some other scan, have it return an insideout scan and a flag that
6078
requests to "fork" this loop iteration. (Q: how does that behave
6079
when the depth is insufficient??)
6081
/* Find the best access method from 's' to the current partial plan */
6082
best_access_path(join, s, session, remaining_tables, idx,
6083
record_count, read_time);
6084
/* Compute the cost of extending the plan with 's' */
6085
current_record_count= record_count * join->positions[idx].records_read;
6086
current_read_time= read_time + join->positions[idx].read_time;
6088
/* Expand only partial plans with lower cost than the best QEP so far */
6089
if ((current_read_time +
6090
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
6092
restore_prev_nj_state(s);
6093
restore_prev_sj_state(remaining_tables, s);
6098
Prune some less promising partial plans. This heuristic may miss
6099
the optimal QEPs, thus it results in a non-exhaustive search.
6101
if (prune_level == 1)
6103
if (best_record_count > current_record_count ||
6104
best_read_time > current_read_time ||
6105
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
6107
if (best_record_count >= current_record_count &&
6108
best_read_time >= current_read_time &&
6109
/* TODO: What is the reasoning behind this condition? */
6110
(!(s->key_dependent & remaining_tables) ||
6111
join->positions[idx].records_read < 2.0))
6113
best_record_count= current_record_count;
6114
best_read_time= current_read_time;
6119
restore_prev_nj_state(s);
6120
restore_prev_sj_state(remaining_tables, s);
6125
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
6126
{ /* Recursively expand the current partial plan */
6127
std::swap(join->best_ref[idx], *pos);
6128
if (best_extension_by_limited_search(join,
6129
remaining_tables & ~real_table_bit,
6131
current_record_count,
6136
std::swap(join->best_ref[idx], *pos);
6140
'join' is either the best partial QEP with 'search_depth' relations,
6141
or the best complete QEP so far, whichever is smaller.
6143
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
6144
if (join->sort_by_table &&
6145
join->sort_by_table !=
6146
join->positions[join->const_tables].table->table)
6147
/* We have to make a temp table */
6148
current_read_time+= current_record_count;
6149
if ((search_depth == 1) || (current_read_time < join->best_read))
6151
memcpy(join->best_positions, join->positions,
6152
sizeof(POSITION) * (idx + 1));
6153
join->best_read= current_read_time - 0.001;
6156
restore_prev_nj_state(s);
6157
restore_prev_sj_state(remaining_tables, s);
6166
- TODO: this function is here only temporarily until 'greedy_search' is
6167
tested and accepted.
6174
find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count,
6177
Session *session= join->session;
6178
if (session->killed)
6182
read_time+=record_count/(double) TIME_FOR_COMPARE;
6183
if (join->sort_by_table &&
6184
join->sort_by_table !=
6185
join->positions[join->const_tables].table->table)
6186
read_time+=record_count; // We have to make a temp table
6187
if (read_time < join->best_read)
6189
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
6190
join->best_read= read_time - 0.001;
6194
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
6195
return(false); /* Found better before */
6198
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
6199
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
6201
table_map real_table_bit=s->table->map;
6202
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
6203
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6205
double records, best;
6206
advance_sj_state(rest_tables, s);
6207
best_access_path(join, s, session, rest_tables, idx, record_count,
6209
records= join->positions[idx].records_read;
6210
best= join->positions[idx].read_time;
6212
Go to the next level only if there hasn't been a better key on
6213
this level! This will cut down the search for a lot simple cases!
6215
double current_record_count=record_count*records;
6216
double current_read_time=read_time+best;
6217
if (best_record_count > current_record_count ||
6218
best_read_time > current_read_time ||
6219
(idx == join->const_tables && s->table == join->sort_by_table))
6221
if (best_record_count >= current_record_count &&
6222
best_read_time >= current_read_time &&
6223
(!(s->key_dependent & rest_tables) || records < 2.0))
6225
best_record_count=current_record_count;
6226
best_read_time=current_read_time;
6228
std::swap(join->best_ref[idx], *pos);
6229
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
6230
current_record_count,current_read_time))
6232
std::swap(join->best_ref[idx], *pos);
6234
restore_prev_nj_state(s);
6235
restore_prev_sj_state(rest_tables, s);
6236
if (join->select_options & SELECT_STRAIGHT_JOIN)
6237
break; // Don't test all combinations
849
6245
Find how much space the prevous read not const tables takes in cache.
851
void calc_used_field_length(Session *, JoinTable *join_tab)
6248
static void calc_used_field_length(Session *, JOIN_TAB *join_tab)
853
6250
uint32_t null_fields,blobs,fields,rec_length;
854
6251
Field **f_ptr,*field;
6252
MY_BITMAP *read_set= join_tab->table->read_set;;
856
6254
null_fields= blobs= fields= rec_length=0;
857
for (f_ptr=join_tab->table->getFields() ; (field= *f_ptr) ; f_ptr++)
6255
for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++)
859
if (field->isReadSet())
6257
if (bitmap_is_set(read_set, field->field_index))
861
6259
uint32_t flags=field->flags;
863
6261
rec_length+=field->pack_length();
864
6262
if (flags & BLOB_FLAG)
866
6264
if (!(flags & NOT_NULL_FLAG))
870
6268
if (null_fields)
873
6271
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
6274
uint32_t blob_length=(uint) (join_tab->table->file->stats.mean_rec_length-
6275
(join_tab->table->getRecordLength()- rec_length));
6276
rec_length+=(uint) cmax((uint)4,blob_length);
6278
join_tab->used_fields=fields;
6279
join_tab->used_fieldlength=rec_length;
6280
join_tab->used_blobs=blobs;
6285
cache_record_length(JOIN *join,uint32_t idx)
6288
JOIN_TAB **pos,**end;
6289
Session *session=join->session;
6291
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
6295
JOIN_TAB *join_tab= *pos;
6296
if (!join_tab->used_fieldlength) /* Not calced yet */
6297
calc_used_field_length(session, join_tab);
6298
length+=join_tab->used_fieldlength;
6305
Get the number of different row combinations for subset of partial join
6309
join The join structure
6310
idx Number of tables in the partial join order (i.e. the
6311
partial join order is in join->positions[0..idx-1])
6312
found_ref Bitmap of tables for which we need to find # of distinct
6316
Given a partial join order (in join->positions[0..idx-1]) and a subset of
6317
tables within that join order (specified in found_ref), find out how many
6318
distinct row combinations of subset tables will be in the result of the
6321
This is used as follows: Suppose we have a table accessed with a ref-based
6322
method. The ref access depends on current rows of tables in found_ref.
6323
We want to count # of different ref accesses. We assume two ref accesses
6324
will be different if at least one of access parameters is different.
6325
Example: consider a query
6327
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
6330
t1, ref access on t1.key=c1
6331
t2, ref access on t2.key=c2
6332
t3, ref access on t3.key=t1.field
6334
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
6335
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
6336
For t3: n_ref_scans = records_read(t1)*records_read(t2)
6337
n_distinct_ref_scans = #records_read(t1)
6339
The reason for having this function (at least the latest version of it)
6340
is that we need to account for buffering in join execution.
6342
An edge-case example: if we have a non-first table in join accessed via
6343
ref(const) or ref(param) where there is a small number of different
6344
values of param, then the access will likely hit the disk cache and will
6345
not require any disk seeks.
6347
The proper solution would be to assume an LRU disk cache of some size,
6348
calculate probability of cache hits, etc. For now we just count
6349
identical ref accesses as one.
6352
Expected number of row combinations
6356
prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
6359
POSITION *pos_end= join->positions - 1;
6360
for (POSITION *pos= join->positions + idx - 1; pos != pos_end; pos--)
6362
if (pos->table->table->map & found_ref)
6364
found_ref|= pos->ref_depend_map;
6366
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
6367
with no matching row we will get position[t2].records_read==0.
6368
Actually the size of output is one null-complemented row, therefore
6369
we will use value of 1 whenever we get records_read==0.
6372
- the above case can't occur if inner part of outer join has more
6373
than one table: table with no matches will not be marked as const.
6375
- Ideally we should add 1 to records_read for every possible null-
6376
complemented row. We're not doing it because: 1. it will require
6377
non-trivial code and add overhead. 2. The value of records_read
6378
is an inprecise estimate and adding 1 (or, in the worst case,
6379
#max_nested_outer_joins=64-1) will not make it any more precise.
6381
if (pos->records_read > DBL_EPSILON)
6382
found*= pos->records_read;
6390
Set up join struct according to best position.
6394
get_best_combination(JOIN *join)
6397
table_map used_tables;
6398
JOIN_TAB *join_tab,*j;
6400
uint32_t table_count;
6401
Session *session=join->session;
6403
table_count=join->tables;
6404
if (!(join->join_tab=join_tab=
6405
(JOIN_TAB*) session->alloc(sizeof(JOIN_TAB)*table_count)))
6410
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
6411
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
6414
*j= *join->best_positions[tablenr].table;
6415
form=join->table[tablenr]=j->table;
6416
used_tables|= form->map;
6417
form->reginfo.join_tab=j;
6418
if (!*j->on_expr_ref)
6419
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
6420
if (j->type == JT_CONST)
6421
continue; // Handled in make_join_stat..
6426
if (j->type == JT_SYSTEM)
6428
if (j->keys.is_clear_all() || !(keyuse= join->best_positions[tablenr].key))
6431
if (tablenr != join->const_tables)
6434
else if (create_ref_for_key(join, j, keyuse, used_tables))
6435
return(true); // Something went wrong
6438
for (i=0 ; i < table_count ; i++)
6439
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
6440
update_depend_map(join);
6445
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
6446
table_map used_tables)
6448
KEYUSE *keyuse=org_keyuse;
6449
Session *session= join->session;
6450
uint32_t keyparts,length,key;
6454
/* Use best key from find_best */
6457
keyinfo=table->key_info+key;
6461
uint32_t found_part_ref_or_null= 0;
6463
Calculate length for the used key
6464
Stop if there is a missing key part or when we find second key_part
6465
with KEY_OPTIMIZE_REF_OR_NULL
6469
if (!(~used_tables & keyuse->used_tables))
6471
if (keyparts == keyuse->keypart &&
6472
!(found_part_ref_or_null & keyuse->optimize))
6475
length+= keyinfo->key_part[keyuse->keypart].store_length;
6476
found_part_ref_or_null|= keyuse->optimize;
6480
} while (keyuse->table == table && keyuse->key == key);
6483
/* set up fieldref */
6484
keyinfo=table->key_info+key;
6485
j->ref.key_parts=keyparts;
6486
j->ref.key_length=length;
6487
j->ref.key=(int) key;
6488
if (!(j->ref.key_buff= (unsigned char*) session->calloc(ALIGN_SIZE(length)*2)) ||
6489
!(j->ref.key_copy= (store_key**) session->alloc((sizeof(store_key*) *
6491
!(j->ref.items= (Item**) session->alloc(sizeof(Item*)*keyparts)) ||
6492
!(j->ref.cond_guards= (bool**) session->alloc(sizeof(uint*)*keyparts)))
6496
j->ref.key_buff2=j->ref.key_buff+ALIGN_SIZE(length);
6498
j->ref.null_rejecting= 0;
6499
j->ref.disable_cache= false;
6502
store_key **ref_key= j->ref.key_copy;
6503
unsigned char *key_buff=j->ref.key_buff, *null_ref_key= 0;
6504
bool keyuse_uses_no_tables= true;
6507
for (i=0 ; i < keyparts ; keyuse++,i++)
6509
while (keyuse->keypart != i ||
6510
((~used_tables) & keyuse->used_tables))
6511
keyuse++; /* Skip other parts */
6513
uint32_t maybe_null= test(keyinfo->key_part[i].null_bit);
6514
j->ref.items[i]=keyuse->val; // Save for cond removal
6515
j->ref.cond_guards[i]= keyuse->cond_guard;
6516
if (keyuse->null_rejecting)
6517
j->ref.null_rejecting |= 1 << i;
6518
keyuse_uses_no_tables= keyuse_uses_no_tables && !keyuse->used_tables;
6519
if (!keyuse->used_tables &&
6520
!(join->select_options & SELECT_DESCRIBE))
6521
{ // Compare against constant
6522
store_key_item tmp(session, keyinfo->key_part[i].field,
6523
key_buff + maybe_null,
6524
maybe_null ? key_buff : 0,
6525
keyinfo->key_part[i].length, keyuse->val);
6526
if (session->is_fatal_error)
6531
*ref_key++= get_store_key(session,
6532
keyuse,join->const_table_map,
6533
&keyinfo->key_part[i],
6534
key_buff, maybe_null);
6536
Remember if we are going to use REF_OR_NULL
6537
But only if field _really_ can be null i.e. we force JT_REF
6538
instead of JT_REF_OR_NULL in case if field can't be null
6540
if ((keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL) && maybe_null)
6541
null_ref_key= key_buff;
6542
key_buff+=keyinfo->key_part[i].store_length;
6545
*ref_key=0; // end_marker
6546
if (j->type == JT_CONST)
6547
j->table->const_table= 1;
6548
else if (((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) != HA_NOSAME) ||
6549
keyparts != keyinfo->key_parts || null_ref_key)
6551
/* Must read with repeat */
6552
j->type= null_ref_key ? JT_REF_OR_NULL : JT_REF;
6553
j->ref.null_ref_key= null_ref_key;
6555
else if (keyuse_uses_no_tables)
6558
This happen if we are using a constant expression in the ON part
6560
SELECT * FROM a LEFT JOIN b ON b.key=30
6561
Here we should not mark the table as a 'const' as a field may
6562
have a 'normal' value or a NULL value.
6574
get_store_key(Session *session, KEYUSE *keyuse, table_map used_tables,
6575
KEY_PART_INFO *key_part, unsigned char *key_buff, uint32_t maybe_null)
6577
if (!((~used_tables) & keyuse->used_tables)) // if const item
895
6579
return new store_key_const_item(session,
896
6580
key_part->field,
897
6581
key_buff + maybe_null,
898
6582
maybe_null ? key_buff : 0,
899
6583
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))
6586
else if (keyuse->val->type() == Item::FIELD_ITEM ||
6587
(keyuse->val->type() == Item::REF_ITEM &&
6588
((Item_ref*)keyuse->val)->ref_type() == Item_ref::OUTER_REF &&
6589
(*(Item_ref**)((Item_ref*)keyuse->val)->ref)->ref_type() ==
6590
Item_ref::DIRECT_REF &&
6591
keyuse->val->real_item()->type() == Item::FIELD_ITEM))
908
6592
return new store_key_field(session,
909
6593
key_part->field,
910
6594
key_buff + maybe_null,
911
6595
maybe_null ? key_buff : 0,
912
6596
key_part->length,
913
((Item_field*) key_use_val->real_item())->field,
914
key_use_val->full_name());
6597
((Item_field*) keyuse->val->real_item())->field,
6598
keyuse->val->full_name());
916
6599
return new store_key_item(session,
917
6600
key_part->field,
918
6601
key_buff + maybe_null,
919
6602
maybe_null ? key_buff : 0,
920
6603
key_part->length,
6848
Fill in outer join related info for the execution plan structure.
6850
For each outer join operation left after simplification of the
6851
original query the function set up the following pointers in the linear
6852
structure join->join_tab representing the selected execution plan.
6853
The first inner table t0 for the operation is set to refer to the last
6854
inner table tk through the field t0->last_inner.
6855
Any inner table ti for the operation are set to refer to the first
6856
inner table ti->first_inner.
6857
The first inner table t0 for the operation is set to refer to the
6858
first inner table of the embedding outer join operation, if there is any,
6859
through the field t0->first_upper.
6860
The on expression for the outer join operation is attached to the
6861
corresponding first inner table through the field t0->on_expr_ref.
6862
Here ti are structures of the JOIN_TAB type.
6864
EXAMPLE. For the query:
6868
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
6869
ON (t1.a=t2.a AND t1.b=t3.b)
6873
given the execution plan with the table order t1,t2,t3,t4
6874
is selected, the following references will be set;
6875
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
6876
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
6877
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
6878
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
6880
@param join reference to the info fully describing the query
6883
The function assumes that the simplification procedure has been
6884
already applied to the join query (see simplify_joins).
6885
This function can be called only after the execution plan
6890
make_outerjoin_info(JOIN *join)
6892
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6894
JOIN_TAB *tab=join->join_tab+i;
6895
Table *table=tab->table;
6896
TableList *tbl= table->pos_in_table_list;
6897
TableList *embedding= tbl->embedding;
6899
if (tbl->outer_join)
6902
Table tab is the only one inner table for outer join.
6903
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
6904
is in the query above.)
6906
tab->last_inner= tab->first_inner= tab;
6907
tab->on_expr_ref= &tbl->on_expr;
6908
tab->cond_equal= tbl->cond_equal;
6910
tab->first_upper= embedding->nested_join->first_nested;
6912
for ( ; embedding ; embedding= embedding->embedding)
6914
/* Ignore sj-nests: */
6915
if (!embedding->on_expr)
6917
nested_join_st *nested_join= embedding->nested_join;
6918
if (!nested_join->counter_)
6921
Table tab is the first inner table for nested_join.
6922
Save reference to it in the nested join structure.
6924
nested_join->first_nested= tab;
6925
tab->on_expr_ref= &embedding->on_expr;
6926
tab->cond_equal= tbl->cond_equal;
6927
if (embedding->embedding)
6928
tab->first_upper= embedding->embedding->nested_join->first_nested;
6930
if (!tab->first_inner)
6931
tab->first_inner= nested_join->first_nested;
6932
if (++nested_join->counter_ < nested_join->join_list.elements)
6934
/* Table tab is the last inner table for nested join. */
6935
nested_join->first_nested->last_inner= tab;
6943
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
6945
Session *session= join->session;
6948
add_not_null_conds(join);
6949
table_map used_tables;
6950
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
6951
{ /* there may be a select without a cond. */
6952
if (join->tables > 1)
6953
cond->update_used_tables(); // Tablenr may have changed
6954
if (join->const_tables == join->tables &&
6955
session->lex->current_select->master_unit() ==
6956
&session->lex->unit) // not upper level SELECT
6957
join->const_table_map|=RAND_TABLE_BIT;
6958
{ // Check const tables
6960
make_cond_for_table(cond,
6961
join->const_table_map,
6963
for (JOIN_TAB *tab= join->join_tab+join->const_tables;
6964
tab < join->join_tab+join->tables ; tab++)
6966
if (*tab->on_expr_ref)
6968
JOIN_TAB *cond_tab= tab->first_inner;
6969
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
6970
join->const_table_map,
6974
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
6977
tmp->quick_fix_field();
6978
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
6979
new Item_cond_and(cond_tab->select_cond,
6981
if (!cond_tab->select_cond)
6983
cond_tab->select_cond->quick_fix_field();
6986
if (const_cond && !const_cond->val_int())
6988
return(1); // Impossible const condition
6992
used_tables=((select->const_tables=join->const_table_map) |
6993
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
6994
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6996
JOIN_TAB *tab=join->join_tab+i;
6998
first_inner is the X in queries like:
6999
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
7001
JOIN_TAB *first_inner_tab= tab->first_inner;
7002
table_map current_map= tab->table->map;
7003
bool use_quick_range=0;
7007
Following force including random expression in last table condition.
7008
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
7010
if (i == join->tables-1)
7011
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
7012
used_tables|=current_map;
7014
if (tab->type == JT_REF && tab->quick &&
7015
(uint) tab->ref.key == tab->quick->index &&
7016
tab->ref.key_length < tab->quick->max_used_key_length)
7018
/* Range uses longer key; Use this instead of ref on key */
7023
tab->ref.key_parts=0; // Don't use ref key.
7024
join->best_positions[i].records_read= rows2double(tab->quick->records);
7026
We will use join cache here : prevent sorting of the first
7027
table only and sort at the end.
7029
if (i != join->const_tables && join->tables > join->const_tables + 1)
7035
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
7036
if (cond && !tmp && tab->quick)
7038
if (tab->type != JT_ALL)
7041
Don't use the quick method
7042
We come here in the case where we have 'key=constant' and
7043
the test is removed by make_cond_for_table()
7051
Hack to handle the case where we only refer to a table
7052
in the ON part of an OUTER JOIN. In this case we want the code
7053
below to check if we should use 'quick' instead.
7055
tmp= new Item_int((int64_t) 1,1); // Always true
7059
if (tmp || !cond || tab->type == JT_REF || tab->type == JT_REF_OR_NULL ||
7060
tab->type == JT_EQ_REF)
7062
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
7063
session->memdup((unsigned char*) select,
7066
return(1); // End of memory
7068
If tab is an inner table of an outer join operation,
7069
add a match guard to the pushed down predicate.
7070
The guard will turn the predicate on only after
7071
the first match for outer tables is encountered.
7076
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
7077
a cond, so neutralize the hack above.
7079
if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
7081
tab->select_cond=sel->cond=tmp;
7082
/* Push condition to storage engine if this is enabled
7083
and the condition is not guarded */
7084
tab->table->file->pushed_cond= NULL;
7085
if (session->variables.engine_condition_pushdown)
7088
make_cond_for_table(tmp, current_map, current_map, 0);
7091
/* Push condition to handler */
7092
if (!tab->table->file->cond_push(push_cond))
7093
tab->table->file->pushed_cond= push_cond;
7098
tab->select_cond= sel->cond= NULL;
7100
sel->head=tab->table;
7103
/* Use quick key read if it's a constant and it's not used
7105
if (tab->needed_reg.is_clear_all() && tab->type != JT_EQ_REF
7106
&& (tab->type != JT_REF || (uint) tab->ref.key == tab->quick->index))
7108
sel->quick=tab->quick; // Use value from get_quick_...
7109
sel->quick_keys.clear_all();
7110
sel->needed_reg.clear_all();
7118
uint32_t ref_key=(uint) sel->head->reginfo.join_tab->ref.key+1;
7119
if (i == join->const_tables && ref_key)
7121
if (!tab->const_keys.is_clear_all() &&
7122
tab->table->reginfo.impossible_range)
7125
else if (tab->type == JT_ALL && ! use_quick_range)
7127
if (!tab->const_keys.is_clear_all() &&
7128
tab->table->reginfo.impossible_range)
7129
return(1); // Impossible range
7131
We plan to scan all rows.
7132
Check again if we should use an index.
7133
We could have used an column from a previous table in
7134
the index if we are using limit and this is the first table
7137
if ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||
7138
(!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)))
7140
/* Join with outer join condition */
7141
COND *orig_cond=sel->cond;
7142
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
7145
We can't call sel->cond->fix_fields,
7146
as it will break tab->on_expr if it's AND condition
7147
(fix_fields currently removes extra AND/OR levels).
7148
Yet attributes of the just built condition are not needed.
7149
Thus we call sel->cond->quick_fix_field for safety.
7151
if (sel->cond && !sel->cond->fixed)
7152
sel->cond->quick_fix_field();
7154
if (sel->test_quick_select(session, tab->keys,
7155
used_tables & ~ current_map,
7156
(join->select_options &
7159
join->unit->select_limit_cnt), 0,
7163
Before reporting "Impossible WHERE" for the whole query
7164
we have to check isn't it only "impossible ON" instead
7166
sel->cond=orig_cond;
7167
if (!*tab->on_expr_ref ||
7168
sel->test_quick_select(session, tab->keys,
7169
used_tables & ~ current_map,
7170
(join->select_options &
7173
join->unit->select_limit_cnt),0,
7175
return(1); // Impossible WHERE
7178
sel->cond=orig_cond;
7180
/* Fix for EXPLAIN */
7182
join->best_positions[i].records_read= (double)sel->quick->records;
7186
sel->needed_reg=tab->needed_reg;
7187
sel->quick_keys.clear_all();
7189
if (!sel->quick_keys.is_subset(tab->checked_keys) ||
7190
!sel->needed_reg.is_subset(tab->checked_keys))
7192
tab->keys=sel->quick_keys;
7193
tab->keys.merge(sel->needed_reg);
7194
tab->use_quick= (!sel->needed_reg.is_clear_all() &&
7195
(select->quick_keys.is_clear_all() ||
7197
(select->quick->records >= 100L)))) ?
7199
sel->read_tables= used_tables & ~current_map;
7201
if (i != join->const_tables && tab->use_quick != 2)
7202
{ /* Read with cache */
7204
(tmp=make_cond_for_table(cond,
7205
join->const_table_map |
7209
tab->cache.select=(SQL_SELECT*)
7210
session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
7211
tab->cache.select->cond=tmp;
7212
tab->cache.select->read_tables=join->const_table_map;
7219
Push down conditions from all on expressions.
7220
Each of these conditions are guarded by a variable
7221
that turns if off just before null complemented row for
7222
outer joins is formed. Thus, the condition from an
7223
'on expression' are guaranteed not to be checked for
7224
the null complemented row.
7227
/* First push down constant conditions from on expressions */
7228
for (JOIN_TAB *join_tab= join->join_tab+join->const_tables;
7229
join_tab < join->join_tab+join->tables ; join_tab++)
7231
if (*join_tab->on_expr_ref)
7233
JOIN_TAB *cond_tab= join_tab->first_inner;
7234
COND *tmp= make_cond_for_table(*join_tab->on_expr_ref,
7235
join->const_table_map,
7239
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
7242
tmp->quick_fix_field();
7243
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
7244
new Item_cond_and(cond_tab->select_cond,tmp);
7245
if (!cond_tab->select_cond)
7247
cond_tab->select_cond->quick_fix_field();
7251
/* Push down non-constant conditions from on expressions */
7252
JOIN_TAB *last_tab= tab;
7253
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
7256
Table tab is the last inner table of an outer join.
7257
An on expression is always attached to it.
7259
COND *on_expr= *first_inner_tab->on_expr_ref;
7261
table_map used_tables2= (join->const_table_map |
7262
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7263
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
7265
current_map= tab->table->map;
7266
used_tables2|= current_map;
7267
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
7271
JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
7273
First add the guards for match variables of
7274
all embedding outer join operations.
7276
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
7281
Now add the guard turning the predicate off for
7282
the null complemented row.
7284
tmp_cond= new Item_func_trig_cond(tmp_cond,
7288
tmp_cond->quick_fix_field();
7289
/* Add the predicate to other pushed down predicates */
7290
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
7291
new Item_cond_and(cond_tab->select_cond,
7293
if (!cond_tab->select_cond)
7295
cond_tab->select_cond->quick_fix_field();
7298
first_inner_tab= first_inner_tab->first_upper;
7307
Check if given expression uses only table fields covered by the given index
7310
uses_index_fields_only()
7311
item Expression to check
7312
tbl The table having the index
7313
keyno The index number
7314
other_tbls_ok true <=> Fields of other non-const tables are allowed
7317
Check if given expression only uses fields covered by index #keyno in the
7318
table tbl. The expression can use any fields in any other tables.
7320
The expression is guaranteed not to be AND or OR - those constructs are
7321
handled outside of this function.
7328
bool uses_index_fields_only(Item *item, Table *tbl, uint32_t keyno,
7331
if (item->const_item())
7335
Don't push down the triggered conditions. Nested outer joins execution
7336
code may need to evaluate a condition several times (both triggered and
7337
untriggered), and there is no way to put thi
7338
TODO: Consider cloning the triggered condition and using the copies for:
7339
1. push the first copy down, to have most restrictive index condition
7341
2. Put the second copy into tab->select_cond.
7343
if (item->type() == Item::FUNC_ITEM &&
7344
((Item_func*)item)->functype() == Item_func::TRIG_COND_FUNC)
7347
if (!(item->used_tables() & tbl->map))
7348
return other_tbls_ok;
7350
Item::Type item_type= item->type();
7351
switch (item_type) {
7352
case Item::FUNC_ITEM:
7354
/* This is a function, apply condition recursively to arguments */
7355
Item_func *item_func= (Item_func*)item;
7357
Item **item_end= (item_func->arguments()) + item_func->argument_count();
7358
for (child= item_func->arguments(); child != item_end; child++)
7360
if (!uses_index_fields_only(*child, tbl, keyno, other_tbls_ok))
7365
case Item::COND_ITEM:
7367
/* This is a function, apply condition recursively to arguments */
7368
List_iterator<Item> li(*((Item_cond*)item)->argument_list());
7372
if (!uses_index_fields_only(item, tbl, keyno, other_tbls_ok))
7377
case Item::FIELD_ITEM:
7379
Item_field *item_field= (Item_field*)item;
7380
if (item_field->field->table != tbl)
7382
return item_field->field->part_of_key.is_set(keyno);
7384
case Item::REF_ITEM:
7385
return uses_index_fields_only(item->real_item(), tbl, keyno,
7388
return false; /* Play it safe, don't push unknown non-const items */
1216
7393
#define ICP_COND_USES_INDEX_ONLY 10
1222
void JoinTable::cleanup()
1224
safe_delete(select);
7396
Get a part of the condition that can be checked using only index fields
7399
make_cond_for_index()
7400
cond The source condition
7401
table The table that is partially available
7402
keyno The index in the above table. Only fields covered by the index
7404
other_tbls_ok true <=> Fields of other non-const tables are allowed
7407
Get a part of the condition that can be checked when for the given table
7408
we have values only of fields covered by some index. The condition may
7409
refer to other tables, it is assumed that we have values of all of their
7413
make_cond_for_index(
7414
"cond(t1.field) AND cond(t2.key1) AND cond(t2.non_key) AND cond(t2.key2)",
7417
"cond(t1.field) AND cond(t2.key2)"
7420
Index condition, or NULL if no condition could be inferred.
7423
Item *make_cond_for_index(Item *cond, Table *table, uint32_t keyno,
7428
if (cond->type() == Item::COND_ITEM)
7430
uint32_t n_marked= 0;
7431
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7433
Item_cond_and *new_cond=new Item_cond_and;
7436
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7440
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7442
new_cond->argument_list()->push_back(fix);
7443
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7445
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7446
cond->marker= ICP_COND_USES_INDEX_ONLY;
7447
switch (new_cond->argument_list()->elements) {
7451
return new_cond->argument_list()->head();
7453
new_cond->quick_fix_field();
7459
Item_cond_or *new_cond=new Item_cond_or;
7462
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7466
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7469
new_cond->argument_list()->push_back(fix);
7470
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7472
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7473
cond->marker= ICP_COND_USES_INDEX_ONLY;
7474
new_cond->quick_fix_field();
7475
new_cond->top_level_item();
7480
if (!uses_index_fields_only(cond, table, keyno, other_tbls_ok))
7482
cond->marker= ICP_COND_USES_INDEX_ONLY;
7487
Item *make_cond_remainder(Item *cond, bool exclude_index)
7489
if (exclude_index && cond->marker == ICP_COND_USES_INDEX_ONLY)
7490
return 0; /* Already checked */
7492
if (cond->type() == Item::COND_ITEM)
7494
table_map tbl_map= 0;
7495
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7497
/* Create new top level AND item */
7498
Item_cond_and *new_cond=new Item_cond_and;
7501
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7505
Item *fix= make_cond_remainder(item, exclude_index);
7508
new_cond->argument_list()->push_back(fix);
7509
tbl_map |= fix->used_tables();
7512
switch (new_cond->argument_list()->elements) {
7516
return new_cond->argument_list()->head();
7518
new_cond->quick_fix_field();
7519
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7525
Item_cond_or *new_cond=new Item_cond_or;
7528
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7532
Item *fix= make_cond_remainder(item, false);
7535
new_cond->argument_list()->push_back(fix);
7536
tbl_map |= fix->used_tables();
7538
new_cond->quick_fix_field();
7539
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7540
new_cond->top_level_item();
7549
Try to extract and push the index condition
7553
tab A join tab that has tab->table->file and its condition
7555
keyno Index for which extract and push the condition
7556
other_tbls_ok true <=> Fields of other non-const tables are allowed
7559
Try to extract and push the index condition down to table handler
7562
static void push_index_cond(JOIN_TAB *tab, uint32_t keyno, bool other_tbls_ok)
7565
if (tab->table->file->index_flags(keyno, 0, 1) & HA_DO_INDEX_COND_PUSHDOWN &&
7566
tab->join->session->variables.engine_condition_pushdown)
7568
idx_cond= make_cond_for_index(tab->select_cond, tab->table, keyno,
7573
tab->pre_idx_push_select_cond= tab->select_cond;
7574
Item *idx_remainder_cond=
7575
tab->table->file->idx_cond_push(keyno, idx_cond);
7578
Disable eq_ref's "lookup cache" if we've pushed down an index
7580
TODO: This check happens to work on current ICP implementations, but
7581
there may exist a compliant implementation that will not work
7582
correctly with it. Sort this out when we stabilize the condition
7585
if (idx_remainder_cond != idx_cond)
7586
tab->ref.disable_cache= true;
7588
Item *row_cond= make_cond_remainder(tab->select_cond, true);
7592
if (!idx_remainder_cond)
7593
tab->select_cond= row_cond;
7596
tab->select_cond= new Item_cond_and(row_cond, idx_remainder_cond);
7597
tab->select_cond->quick_fix_field();
7598
((Item_cond_and*)tab->select_cond)->used_tables_cache=
7599
row_cond->used_tables() | idx_remainder_cond->used_tables();
7603
tab->select_cond= idx_remainder_cond;
7606
tab->select->cond= tab->select_cond;
7616
Determine if the set is already ordered for order_st BY, so it can
7617
disable join cache because it will change the ordering of the results.
7618
Code handles sort table that is at any location (not only first after
7619
the const tables) despite the fact that it's currently prohibited.
7620
We must disable join cache if the first non-const table alone is
7621
ordered. If there is a temp table the ordering is done as a last
7622
operation and doesn't prevent join cache usage.
7624
uint32_t make_join_orderinfo(JOIN *join)
7628
return join->tables;
7630
for (i=join->const_tables ; i < join->tables ; i++)
7632
JOIN_TAB *tab=join->join_tab+i;
7633
Table *table=tab->table;
7634
if ((table == join->sort_by_table &&
7635
(!join->order || join->skip_sort_order)) ||
7636
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
7646
Plan refinement stage: do various set ups for the executioner
7649
make_join_readinfo()
7650
join Join being processed
7651
options Join's options (checking for SELECT_DESCRIBE,
7652
SELECT_NO_JOIN_CACHE)
7653
no_jbuf_after Don't use join buffering after table with this number.
7656
Plan refinement stage: do various set ups for the executioner
7657
- set up use of join buffering
7658
- push index conditions
7659
- increment counters
7664
true - Out of memory
7668
make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
7671
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
7674
for (i=join->const_tables ; i < join->tables ; i++)
7676
JOIN_TAB *tab=join->join_tab+i;
7677
Table *table=tab->table;
7678
bool using_join_cache;
7679
tab->read_record.table= table;
7680
tab->read_record.file=table->file;
7681
tab->next_select=sub_select; /* normal select */
7683
TODO: don't always instruct first table's ref/range access method to
7684
produce sorted output.
7686
tab->sorted= sorted;
7687
sorted= 0; // only first must be sorted
7688
if (tab->insideout_match_tab)
7690
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
7695
switch (tab->type) {
7696
case JT_SYSTEM: // Only happens with left join
7697
table->status=STATUS_NO_RECORD;
7698
tab->read_first_record= join_read_system;
7699
tab->read_record.read_record= join_no_more_records;
7701
case JT_CONST: // Only happens with left join
7702
table->status=STATUS_NO_RECORD;
7703
tab->read_first_record= join_read_const;
7704
tab->read_record.read_record= join_no_more_records;
7705
if (table->covering_keys.is_set(tab->ref.key) &&
7709
table->file->extra(HA_EXTRA_KEYREAD);
7713
table->status=STATUS_NO_RECORD;
7716
delete tab->select->quick;
7717
tab->select->quick=0;
7721
tab->read_first_record= join_read_key;
7722
tab->read_record.read_record= join_no_more_records;
7723
if (table->covering_keys.is_set(tab->ref.key) &&
7727
table->file->extra(HA_EXTRA_KEYREAD);
7730
push_index_cond(tab, tab->ref.key, true);
7732
case JT_REF_OR_NULL:
7734
table->status=STATUS_NO_RECORD;
7737
delete tab->select->quick;
7738
tab->select->quick=0;
7742
if (table->covering_keys.is_set(tab->ref.key) &&
7746
table->file->extra(HA_EXTRA_KEYREAD);
7749
push_index_cond(tab, tab->ref.key, true);
7750
if (tab->type == JT_REF)
7752
tab->read_first_record= join_read_always_key;
7753
tab->read_record.read_record= tab->insideout_match_tab?
7754
join_read_next_same_diff : join_read_next_same;
7758
tab->read_first_record= join_read_always_key_or_null;
7759
tab->read_record.read_record= join_read_next_same_or_null;
7764
If previous table use cache
7765
If the incoming data set is already sorted don't use cache.
7767
table->status=STATUS_NO_RECORD;
7768
using_join_cache= false;
7769
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
7770
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
7771
!tab->insideout_match_tab)
7773
if ((options & SELECT_DESCRIBE) ||
7774
!join_init_cache(join->session,join->join_tab+join->const_tables,
7775
i-join->const_tables))
7777
using_join_cache= true;
7778
tab[-1].next_select=sub_select_cache; /* Patch previous */
7781
/* These init changes read_record */
7782
if (tab->use_quick == 2)
7784
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
7785
tab->read_first_record= join_init_quick_read_record;
7787
status_var_increment(join->session->status_var.select_range_check_count);
7791
tab->read_first_record= join_init_read_record;
7792
if (i == join->const_tables)
7794
if (tab->select && tab->select->quick)
7797
status_var_increment(join->session->status_var.select_range_count);
7801
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
7803
status_var_increment(join->session->status_var.select_scan_count);
7808
if (tab->select && tab->select->quick)
7811
status_var_increment(join->session->status_var.select_full_range_join_count);
7815
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
7817
status_var_increment(join->session->status_var.select_full_join_count);
7820
if (!table->no_keyread)
7822
if (tab->select && tab->select->quick &&
7823
tab->select->quick->index != MAX_KEY && //not index_merge
7824
table->covering_keys.is_set(tab->select->quick->index))
7827
table->file->extra(HA_EXTRA_KEYREAD);
7829
else if (!table->covering_keys.is_clear_all() &&
7830
!(tab->select && tab->select->quick))
7831
{ // Only read index tree
7832
if (!tab->insideout_match_tab)
7835
See bug #26447: "Using the clustered index for a table scan
7836
is always faster than using a secondary index".
7838
if (table->s->primary_key != MAX_KEY &&
7839
table->file->primary_key_is_clustered())
7840
tab->index= table->s->primary_key;
7842
tab->index= table->find_shortest_key(&table->covering_keys);
7844
tab->read_first_record= join_read_first;
7845
tab->type=JT_NEXT; // Read with index_first / index_next
7848
if (tab->select && tab->select->quick &&
7849
tab->select->quick->index != MAX_KEY && ! tab->table->key_read)
7850
push_index_cond(tab, tab->select->quick->index, !using_join_cache);
7854
break; /* purecov: deadcode */
7857
abort(); /* purecov: deadcode */
7860
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
7866
Give error if we some tables are done with a full join.
7868
This is used by multi_table_update and multi_table_delete when running
7871
@param join Join condition
7876
1 Error (full join used)
7879
bool error_if_full_join(JOIN *join)
7881
for (JOIN_TAB *tab=join->join_tab, *end=join->join_tab+join->tables;
7885
if (tab->type == JT_ALL && (!tab->select || !tab->select->quick))
7887
my_message(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE,
7888
ER(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE), MYF(0));
7900
void JOIN_TAB::cleanup()
1227
7906
if (cache.buff)
1229
size_t size= cache.end - cache.buff;
1230
global_join_buffer.sub(size);
1231
7907
free(cache.buff);
2515
9611
if (!(left_const && right_const) &&
2516
9612
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,
9616
resolve_const_item(session, &args[1], args[0]);
9617
func->update_used_tables();
9618
change_cond_ref_to_const(session, save_list, and_father, and_father,
9621
else if (left_const)
9623
resolve_const_item(session, &args[0], args[1]);
9624
func->update_used_tables();
9625
change_cond_ref_to_const(session, save_list, and_father, and_father,
9635
Simplify joins replacing outer joins by inner joins whenever it's
9638
The function, during a retrieval of join_list, eliminates those
9639
outer joins that can be converted into inner join, possibly nested.
9640
It also moves the on expressions for the converted outer joins
9641
and from inner joins to conds.
9642
The function also calculates some attributes for nested joins:
9646
- on_expr_dep_tables
9647
The first two attributes are used to test whether an outer join can
9648
be substituted for an inner join. The third attribute represents the
9649
relation 'to be dependent on' for tables. If table t2 is dependent
9650
on table t1, then in any evaluated execution plan table access to
9651
table t2 must precede access to table t2. This relation is used also
9652
to check whether the query contains invalid cross-references.
9653
The forth attribute is an auxiliary one and is used to calculate
9655
As the attribute dep_tables qualifies possibles orders of tables in the
9656
execution plan, the dependencies required by the straight join
9657
modifiers are reflected in this attribute as well.
9658
The function also removes all braces that can be removed from the join
9659
expression without changing its meaning.
9662
An outer join can be replaced by an inner join if the where condition
9663
or the on expression for an embedding nested join contains a conjunctive
9664
predicate rejecting null values for some attribute of the inner tables.
9668
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9670
the predicate t2.b < 5 rejects nulls.
9671
The query is converted first to:
9673
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9675
then to the equivalent form:
9677
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
9681
Similarly the following query:
9683
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
9688
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
9692
One conversion might trigger another:
9694
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
9695
LEFT JOIN t3 ON t3.b=t2.b
9696
WHERE t3 IS NOT NULL =>
9697
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
9698
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
9699
SELECT * FROM t1, t2, t3
9700
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
9703
The function removes all unnecessary braces from the expression
9704
produced by the conversions.
9707
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9709
finally is converted to:
9711
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9716
It also will remove braces from the following queries:
9718
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
9719
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
9722
The benefit of this simplification procedure is that it might return
9723
a query for which the optimizer can evaluate execution plan with more
9724
join orders. With a left join operation the optimizer does not
9725
consider any plan where one of the inner tables is before some of outer
9729
The function is implemented by a recursive procedure. On the recursive
9730
ascent all attributes are calculated, all outer joins that can be
9731
converted are replaced and then all unnecessary braces are removed.
9732
As join list contains join tables in the reverse order sequential
9733
elimination of outer joins does not require extra recursive calls.
9736
Remove all semi-joins that have are within another semi-join (i.e. have
9737
an "ancestor" semi-join nest)
9740
Here is an example of a join query with invalid cross references:
9742
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
9745
@param join reference to the query info
9746
@param join_list list representation of the join to be converted
9747
@param conds conditions to add on expressions for converted joins
9748
@param top true <=> conds is the where condition
9751
- The new condition, if success
9756
simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top,
9760
nested_join_st *nested_join;
9761
TableList *prev_table= 0;
9762
List_iterator<TableList> li(*join_list);
9765
Try to simplify join operations from join_list.
9766
The most outer join operation is checked for conversion first.
9768
while ((table= li++))
9770
table_map used_tables;
9771
table_map not_null_tables= (table_map) 0;
9773
if ((nested_join= table->nested_join))
9776
If the element of join_list is a nested join apply
9777
the procedure to its nested join list first.
9781
Item *expr= table->on_expr;
9783
If an on expression E is attached to the table,
9784
check all null rejected predicates in this expression.
9785
If such a predicate over an attribute belonging to
9786
an inner table of an embedded outer join is found,
9787
the outer join is converted to an inner join and
9788
the corresponding on expression is added to E.
9790
expr= simplify_joins(join, &nested_join->join_list,
9791
expr, false, in_sj || table->sj_on_expr);
9793
if (!table->prep_on_expr || expr != table->on_expr)
9797
table->on_expr= expr;
9798
table->prep_on_expr= expr->copy_andor_structure(join->session);
9801
nested_join->used_tables= (table_map) 0;
9802
nested_join->not_null_tables=(table_map) 0;
9803
conds= simplify_joins(join, &nested_join->join_list, conds, top,
9804
in_sj || table->sj_on_expr);
9805
used_tables= nested_join->used_tables;
9806
not_null_tables= nested_join->not_null_tables;
9810
if (!table->prep_on_expr)
9811
table->prep_on_expr= table->on_expr;
9812
used_tables= table->table->map;
9814
not_null_tables= conds->not_null_tables();
9817
if (table->embedding)
9819
table->embedding->nested_join->used_tables|= used_tables;
9820
table->embedding->nested_join->not_null_tables|= not_null_tables;
9823
if (!table->outer_join || (used_tables & not_null_tables))
9826
For some of the inner tables there are conjunctive predicates
9827
that reject nulls => the outer join can be replaced by an inner join.
9829
table->outer_join= 0;
9832
/* Add ON expression to the WHERE or upper-level ON condition. */
9835
conds= and_conds(conds, table->on_expr);
9836
conds->top_level_item();
9837
/* conds is always a new item as both cond and on_expr existed */
9838
assert(!conds->fixed);
9839
conds->fix_fields(join->session, &conds);
9842
conds= table->on_expr;
9843
table->prep_on_expr= table->on_expr= 0;
9851
Only inner tables of non-convertible outer joins
9852
remain with on_expr.
9856
table->dep_tables|= table->on_expr->used_tables();
9857
if (table->embedding)
9859
table->dep_tables&= ~table->embedding->nested_join->used_tables;
9861
Embedding table depends on tables used
9862
in embedded on expressions.
9864
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
9867
table->dep_tables&= ~table->table->map;
9872
/* The order of tables is reverse: prev_table follows table */
9873
if (prev_table->straight)
9874
prev_table->dep_tables|= used_tables;
9875
if (prev_table->on_expr)
9877
prev_table->dep_tables|= table->on_expr_dep_tables;
9878
table_map prev_used_tables= prev_table->nested_join ?
9879
prev_table->nested_join->used_tables :
9880
prev_table->table->map;
9882
If on expression contains only references to inner tables
9883
we still make the inner tables dependent on the outer tables.
9884
It would be enough to set dependency only on one outer table
9885
for them. Yet this is really a rare case.
9887
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
9888
prev_table->dep_tables|= used_tables;
9895
Flatten nested joins that can be flattened.
9896
no ON expression and not a semi-join => can be flattened.
9899
while ((table= li++))
9901
nested_join= table->nested_join;
9902
if (table->sj_on_expr && !in_sj)
9905
If this is a semi-join that is not contained within another semi-join,
9906
leave it intact (otherwise it is flattened)
9908
join->select_lex->sj_nests.push_back(table);
9910
else if (nested_join && !table->on_expr)
9913
List_iterator<TableList> it(nested_join->join_list);
9916
tbl->embedding= table->embedding;
9917
tbl->join_list= table->join_list;
9919
li.replace(nested_join->join_list);
9927
Assign each nested join structure a bit in nested_join_map.
9929
Assign each nested join structure (except "confluent" ones - those that
9930
embed only one element) a bit in nested_join_map.
9932
@param join Join being processed
9933
@param join_list List of tables
9934
@param first_unused Number of first unused bit in nested_join_map before the
9938
This function is called after simplify_joins(), when there are no
9939
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
9940
we will not run out of bits in nested_join_map.
9943
First unused bit in nested_join_map after the call.
9946
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
9947
uint32_t first_unused)
9949
List_iterator<TableList> li(*join_list);
9951
while ((table= li++))
9953
nested_join_st *nested_join;
9954
if ((nested_join= table->nested_join))
9957
It is guaranteed by simplify_joins() function that a nested join
9958
that has only one child is either
9959
- a single-table view (the child is the underlying table), or
9960
- a single-table semi-join nest
9962
We don't assign bits to such sj-nests because
9963
1. it is redundant (a "sequence" of one table cannot be interleaved
9965
2. we could run out bits in nested_join_map otherwise.
9967
if (nested_join->join_list.elements != 1)
9969
/* Don't assign bits to sj-nests */
9971
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
9972
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
9977
return(first_unused);
9982
Set nested_join_st::counter=0 in all nested joins in passed list.
9984
Recursively set nested_join_st::counter=0 for all nested joins contained in
9985
the passed join_list.
9987
@param join_list List of nested joins to process. It may also contain base
9988
tables which will be ignored.
9991
static void reset_nj_counters(List<TableList> *join_list)
9993
List_iterator<TableList> li(*join_list);
9995
while ((table= li++))
9997
nested_join_st *nested_join;
9998
if ((nested_join= table->nested_join))
10000
nested_join->counter_= 0;
10001
reset_nj_counters(&nested_join->join_list);
2538
10009
Check interleaving with an inner tables of an outer join for
3362
int safe_index_read(JoinTable *tab)
10915
SemiJoinDuplicateElimination: Weed out duplicate row combinations
10918
do_sj_dups_weedout()
10922
1 The row combination is a duplicate (discard it)
10923
0 The row combination is not a duplicate (continue)
10926
int do_sj_dups_weedout(Session *session, SJ_TMP_TABLE *sjtbl)
10929
SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
10930
SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
10931
unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;
10932
unsigned char *nulls_ptr= ptr;
10934
/* Put the the rowids tuple into table->record[0]: */
10936
// 1. Store the length
10937
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
10939
*ptr= (unsigned char)(sjtbl->rowid_len + sjtbl->null_bytes);
10944
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
10948
// 2. Zero the null bytes
10949
if (sjtbl->null_bytes)
10951
memset(ptr, 0, sjtbl->null_bytes);
10952
ptr += sjtbl->null_bytes;
10955
// 3. Put the rowids
10956
for (uint32_t i=0; tab != tab_end; tab++, i++)
10958
handler *h= tab->join_tab->table->file;
10959
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
10961
/* It's a NULL-complemented row */
10962
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
10963
memset(ptr + tab->rowid_offset, 0, h->ref_length);
10967
/* Copy the rowid value */
10968
if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
10969
h->position(tab->join_tab->table->record[0]);
10970
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
10974
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
10977
/* create_myisam_from_heap will generate error if needed */
10978
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
10979
create_myisam_from_heap(session, sjtbl->tmp_table, sjtbl->start_recinfo,
10980
&sjtbl->recinfo, error, 1))
10982
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
10990
SemiJoinDuplicateElimination: Reset the temporary table
10993
int do_sj_reset(SJ_TMP_TABLE *sj_tbl)
10995
if (sj_tbl->tmp_table)
10996
return sj_tbl->tmp_table->file->ha_delete_all_rows();
11001
Process one record of the nested loop join.
11003
This function will evaluate parts of WHERE/ON clauses that are
11004
applicable to the partial record on hand and in case of success
11005
submit this record to the next level of the nested loop.
11008
static enum_nested_loop_state
11009
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
11012
bool not_used_in_distinct=join_tab->not_used_in_distinct;
11013
ha_rows found_records=join->found_records;
11014
COND *select_cond= join_tab->select_cond;
11016
if (error > 0 || (join->session->is_error())) // Fatal error
11017
return NESTED_LOOP_ERROR;
11019
return NESTED_LOOP_NO_MORE_ROWS;
11020
if (join->session->killed) // Aborted by user
11022
join->session->send_kill_message();
11023
return NESTED_LOOP_KILLED; /* purecov: inspected */
11025
if (!select_cond || select_cond->val_int())
11028
There is no select condition or the attached pushed down
11029
condition is true => a match is found.
11032
while (join_tab->first_unmatched && found)
11035
The while condition is always false if join_tab is not
11036
the last inner join table of an outer join operation.
11038
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11040
Mark that a match for current outer table is found.
11041
This activates push down conditional predicates attached
11042
to the all inner tables of the outer join.
11044
first_unmatched->found= 1;
11045
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11047
if (tab->table->reginfo.not_exists_optimize)
11048
return NESTED_LOOP_NO_MORE_ROWS;
11049
/* Check all predicates that has just been activated. */
11051
Actually all predicates non-guarded by first_unmatched->found
11052
will be re-evaluated again. It could be fixed, but, probably,
11053
it's not worth doing now.
11055
if (tab->select_cond && !tab->select_cond->val_int())
11057
/* The condition attached to table tab is false */
11058
if (tab == join_tab)
11063
Set a return point if rejected predicate is attached
11064
not to the last table of the current nest level.
11066
join->return_tab= tab;
11067
return NESTED_LOOP_OK;
11072
Check whether join_tab is not the last inner table
11073
for another embedding outer join.
11075
if ((first_unmatched= first_unmatched->first_upper) &&
11076
first_unmatched->last_inner != join_tab)
11077
first_unmatched= 0;
11078
join_tab->first_unmatched= first_unmatched;
11081
JOIN_TAB *return_tab= join->return_tab;
11082
join_tab->found_match= true;
11083
if (join_tab->check_weed_out_table)
11085
int res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table);
11087
return NESTED_LOOP_ERROR;
11089
return NESTED_LOOP_OK;
11091
else if (join_tab->do_firstmatch)
11094
We should return to the join_tab->do_firstmatch after we have
11095
enumerated all the suffixes for current prefix row combination
11097
return_tab= join_tab->do_firstmatch;
11101
It was not just a return to lower loop level when one
11102
of the newly activated predicates is evaluated as false
11103
(See above join->return_tab= tab).
11105
join->examined_rows++;
11106
join->session->row_count++;
11110
enum enum_nested_loop_state rc;
11111
/* A match from join_tab is found for the current partial join. */
11112
rc= (*join_tab->next_select)(join, join_tab+1, 0);
11113
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11115
if (return_tab < join->return_tab)
11116
join->return_tab= return_tab;
11118
if (join->return_tab < join_tab)
11119
return NESTED_LOOP_OK;
11121
Test if this was a SELECT DISTINCT query on a table that
11122
was not in the field list; In this case we can abort if
11123
we found a row, as no new rows can be added to the result.
11125
if (not_used_in_distinct && found_records != join->found_records)
11126
return NESTED_LOOP_NO_MORE_ROWS;
11129
join_tab->read_record.file->unlock_row();
11134
The condition pushed down to the table join_tab rejects all rows
11135
with the beginning coinciding with the current partial join.
11137
join->examined_rows++;
11138
join->session->row_count++;
11139
join_tab->read_record.file->unlock_row();
11141
return NESTED_LOOP_OK;
11148
Construct a NULL complimented partial join record and feed it to the next
11149
level of the nested loop. This function is used in case we have
11150
an OUTER join and no matching record was found.
11153
static enum_nested_loop_state
11154
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab)
11157
The table join_tab is the first inner table of a outer join operation
11158
and no matches has been found for the current outer row.
11160
JOIN_TAB *last_inner_tab= join_tab->last_inner;
11161
/* Cache variables for faster loop */
11163
for ( ; join_tab <= last_inner_tab ; join_tab++)
11165
/* Change the the values of guard predicate variables. */
11166
join_tab->found= 1;
11167
join_tab->not_null_compl= 0;
11168
/* The outer row is complemented by nulls for each inner tables */
11169
restore_record(join_tab->table,s->default_values); // Make empty record
11170
mark_as_null_row(join_tab->table); // For group by without error
11171
select_cond= join_tab->select_cond;
11172
/* Check all attached conditions for inner table rows. */
11173
if (select_cond && !select_cond->val_int())
11174
return NESTED_LOOP_OK;
11178
The row complemented by nulls might be the first row
11179
of embedding outer joins.
11180
If so, perform the same actions as in the code
11181
for the first regular outer join row above.
11185
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11186
if ((first_unmatched= first_unmatched->first_upper) &&
11187
first_unmatched->last_inner != join_tab)
11188
first_unmatched= 0;
11189
join_tab->first_unmatched= first_unmatched;
11190
if (!first_unmatched)
11192
first_unmatched->found= 1;
11193
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11195
if (tab->select_cond && !tab->select_cond->val_int())
11197
join->return_tab= tab;
11198
return NESTED_LOOP_OK;
11203
The row complemented by nulls satisfies all conditions
11204
attached to inner tables.
11205
Send the row complemented by nulls to be joined with the
11208
return (*join_tab->next_select)(join, join_tab+1, 0);
11212
static enum_nested_loop_state
11213
flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skip_last)
11215
enum_nested_loop_state rc= NESTED_LOOP_OK;
11219
join_tab->table->null_row= 0;
11220
if (!join_tab->cache.records)
11221
return NESTED_LOOP_OK; /* Nothing to do */
11223
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
11224
if (join_tab->use_quick == 2)
11226
if (join_tab->select->quick)
11227
{ /* Used quick select last. reset it */
11228
delete join_tab->select->quick;
11229
join_tab->select->quick=0;
11232
/* read through all records */
11233
if ((error=join_init_read_record(join_tab)))
11235
reset_cache_write(&join_tab->cache);
11236
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
11239
for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
11241
tmp->status=tmp->table->status;
11242
tmp->table->status=0;
11245
info= &join_tab->read_record;
11248
if (join->session->killed)
11250
join->session->send_kill_message();
11251
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
11253
SQL_SELECT *select=join_tab->select;
11254
if (rc == NESTED_LOOP_OK &&
11255
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
11258
reset_cache_read(&join_tab->cache);
11259
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
11261
read_cached_record(join_tab);
11262
if (!select || !select->skip_record())
11265
if (!join_tab->check_weed_out_table ||
11266
!(res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table)))
11268
rc= (join_tab->next_select)(join,join_tab+1,0);
11269
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11271
reset_cache_write(&join_tab->cache);
11276
return NESTED_LOOP_ERROR;
11280
} while (!(error=info->read_record(info)));
11283
read_cached_record(join_tab); // Restore current record
11284
reset_cache_write(&join_tab->cache);
11285
if (error > 0) // Fatal error
11286
return NESTED_LOOP_ERROR; /* purecov: inspected */
11287
for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
11288
tmp2->table->status=tmp2->status;
11289
return NESTED_LOOP_OK;
11292
int safe_index_read(JOIN_TAB *tab)
3365
11295
Table *table= tab->table;
3366
if ((error=table->cursor->index_read_map(table->getInsertRecord(),
11296
if ((error=table->file->index_read_map(table->record[0],
3367
11297
tab->ref.key_buff,
3368
11298
make_prev_keypart_map(tab->ref.key_parts),
3369
11299
HA_READ_KEY_EXACT)))
15350
/** Allocate memory needed for other rollup functions. */
15352
bool JOIN::rollup_init()
15357
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
15358
rollup.state= ROLLUP::STATE_INITED;
15361
Create pointers to the different sum function groups
15362
These are updated by rollup_make_fields()
15364
tmp_table_param.group_parts= send_group_parts;
15366
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
15368
sizeof(List<Item>) +
15369
ref_pointer_array_size)
15370
* send_group_parts )))
15373
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
15374
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
15375
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
15378
Prepare space for field list for the different levels
15379
These will be filled up in rollup_make_fields()
15381
for (i= 0 ; i < send_group_parts ; i++)
15383
rollup.null_items[i]= new (session->mem_root) Item_null_result();
15384
List<Item> *rollup_fields= &rollup.fields[i];
15385
rollup_fields->empty();
15386
rollup.ref_pointer_arrays[i]= ref_array;
15387
ref_array+= all_fields.elements;
15389
for (i= 0 ; i < send_group_parts; i++)
15391
for (j=0 ; j < fields_list.elements ; j++)
15392
rollup.fields[i].push_back(rollup.null_items[i]);
15394
List_iterator<Item> it(all_fields);
15396
while ((item= it++))
15398
order_st *group_tmp;
15399
bool found_in_group= 0;
15401
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
15403
if (*group_tmp->item == item)
15405
item->maybe_null= 1;
15407
if (item->const_item())
15410
For ROLLUP queries each constant item referenced in GROUP BY list
15411
is wrapped up into an Item_func object yielding the same value
15412
as the constant item. The objects of the wrapper class are never
15413
considered as constant items and besides they inherit all
15414
properties of the Item_result_field class.
15415
This wrapping allows us to ensure writing constant items
15416
into temporary tables whenever the result of the ROLLUP
15417
operation has to be written into a temporary table, e.g. when
15418
ROLLUP is used together with DISTINCT in the SELECT list.
15419
Usually when creating temporary tables for a intermidiate
15420
result we do not include fields for constant expressions.
15422
Item* new_item= new Item_func_rollup_const(item);
15425
new_item->fix_fields(session, (Item **) 0);
15426
session->change_item_tree(it.ref(), new_item);
15427
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
15429
if (*tmp->item == item)
15430
session->change_item_tree(tmp->item, new_item);
15435
if (item->type() == Item::FUNC_ITEM && !found_in_group)
15437
bool changed= false;
15438
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
15441
We have to prevent creation of a field in a temporary table for
15442
an expression that contains GROUP BY attributes.
15443
Marking the expression item as 'with_sum_func' will ensure this.
15446
item->with_sum_func= 1;
15454
Fill up rollup structures with pointers to fields to use.
15456
Creates copies of item_sum items for each sum level.
15458
@param fields_arg List of all fields (hidden and real ones)
15459
@param sel_fields Pointer to selected fields
15460
@param func Store here a pointer to all fields
15464
In this case func is pointing to next not used element.
15469
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields,
15472
List_iterator_fast<Item> it(fields_arg);
15473
Item *first_field= sel_fields.head();
15477
Create field lists for the different levels
15479
The idea here is to have a separate field list for each rollup level to
15480
avoid all runtime checks of which columns should be NULL.
15482
The list is stored in reverse order to get sum function in such an order
15483
in func that it makes it easy to reset them with init_sum_functions()
15485
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15487
rollup.fields[0] will contain list where a,b,c is NULL
15488
rollup.fields[1] will contain list where b,c is NULL
15490
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
15492
sum_funcs_end[0] points to all sum functions
15493
sum_funcs_end[1] points to all sum functions, except grand totals
15497
for (level=0 ; level < send_group_parts ; level++)
15500
uint32_t pos= send_group_parts - level -1;
15501
bool real_fields= 0;
15503
List_iterator<Item> new_it(rollup.fields[pos]);
15504
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
15505
order_st *start_group;
15507
/* Point to first hidden field */
15508
Item **ref_array= ref_array_start + fields_arg.elements-1;
15510
/* Remember where the sum functions ends for the previous level */
15511
sum_funcs_end[pos+1]= *func;
15513
/* Find the start of the group for this level */
15514
for (i= 0, start_group= group_list ;
15516
start_group= start_group->next)
15520
while ((item= it++))
15522
if (item == first_field)
15524
real_fields= 1; // End of hidden fields
15525
ref_array= ref_array_start;
15528
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
15529
(!((Item_sum*) item)->depended_from() ||
15530
((Item_sum *)item)->depended_from() == select_lex))
15534
This is a top level summary function that must be replaced with
15535
a sum function that is reset for this level.
15537
NOTE: This code creates an object which is not that nice in a
15538
sub select. Fortunately it's not common to have rollup in
15541
item= item->copy_or_same(session);
15542
((Item_sum*) item)->make_unique();
15543
*(*func)= (Item_sum*) item;
15548
/* Check if this is something that is part of this group by */
15549
order_st *group_tmp;
15550
for (group_tmp= start_group, i= pos ;
15551
group_tmp ; group_tmp= group_tmp->next, i++)
15553
if (*group_tmp->item == item)
15556
This is an element that is used by the GROUP BY and should be
15557
set to NULL in this level
15559
Item_null_result *null_item= new (session->mem_root) Item_null_result();
15562
item->maybe_null= 1; // Value will be null sometimes
15563
null_item->result_field= item->get_tmp_table_field();
15572
(void) new_it++; // Point to next item
15573
new_it.replace(item); // Replace previous
15580
sum_funcs_end[0]= *func; // Point to last function
15585
Send all rollup levels higher than the current one to the client.
15589
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15592
@param idx Level we are on:
15593
- 0 = Total sum level
15594
- 1 = First group changed (a)
15595
- 2 = Second group changed (a,b)
15600
1 If send_data_failed()
15603
int JOIN::rollup_send_data(uint32_t idx)
15606
for (i= send_group_parts ; i-- > idx ; )
15608
/* Get reference pointers to sum functions in place */
15609
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15610
ref_pointer_array_size);
15611
if ((!having || having->val_int()))
15613
if (send_records < unit->select_limit_cnt && do_send_rows &&
15614
result->send_data(rollup.fields[i]))
15619
/* Restore ref_pointer_array */
15620
set_items_ref_array(current_ref_pointer_array);
15625
Write all rollup levels higher than the current one to a temp table.
15629
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
15632
@param idx Level we are on:
15633
- 0 = Total sum level
15634
- 1 = First group changed (a)
15635
- 2 = Second group changed (a,b)
15636
@param table reference to temp table
15641
1 if write_data_failed()
15644
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
15647
for (i= send_group_parts ; i-- > idx ; )
15649
/* Get reference pointers to sum functions in place */
15650
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15651
ref_pointer_array_size);
15652
if ((!having || having->val_int()))
15656
List_iterator_fast<Item> it(rollup.fields[i]);
15657
while ((item= it++))
15659
if (item->type() == Item::NULL_ITEM && item->is_result_field())
15660
item->save_in_result_field(1);
15662
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
15663
if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
15665
if (create_myisam_from_heap(session, table_arg,
15666
tmp_table_param.start_recinfo,
15667
&tmp_table_param.recinfo,
15673
/* Restore ref_pointer_array */
15674
set_items_ref_array(current_ref_pointer_array);
15679
clear results if there are not rows found for group
15680
(end_send_group/end_write_group)
15685
clear_tables(this);
15686
copy_fields(&tmp_table_param);
15690
Item_sum *func, **func_ptr= sum_funcs;
15691
while ((func= *(func_ptr++)))
15699
Send a description about what how the select will be done to stdout.
15702
void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
15703
bool distinct,const char *message)
15705
List<Item> field_list;
15706
List<Item> item_list;
15707
Session *session=join->session;
15708
select_result *result=join->result;
15709
Item *item_null= new Item_null();
15710
const CHARSET_INFO * const cs= system_charset_info;
15712
/* Don't log this into the slow query log */
15713
session->server_status&= ~(SERVER_QUERY_NO_INDEX_USED | SERVER_QUERY_NO_GOOD_INDEX_USED);
15714
join->unit->offset_limit_cnt= 0;
15717
NOTE: the number/types of items pushed into item_list must be in sync with
15718
EXPLAIN column types as they're "defined" in Session::send_explain_fields()
15722
item_list.push_back(new Item_int((int32_t)
15723
join->select_lex->select_number));
15724
item_list.push_back(new Item_string(join->select_lex->type,
15725
strlen(join->select_lex->type), cs));
15726
for (uint32_t i=0 ; i < 7; i++)
15727
item_list.push_back(item_null);
15728
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15729
item_list.push_back(item_null);
15731
item_list.push_back(new Item_string(message,strlen(message),cs));
15732
if (result->send_data(item_list))
15735
else if (join->select_lex == join->unit->fake_select_lex)
15738
here we assume that the query will return at least two rows, so we
15739
show "filesort" in EXPLAIN. Of course, sometimes we'll be wrong
15740
and no filesort will be actually done, but executing all selects in
15741
the UNION to provide precise EXPLAIN information will hardly be
15744
char table_name_buffer[NAME_LEN];
15747
item_list.push_back(new Item_null);
15749
item_list.push_back(new Item_string(join->select_lex->type,
15750
strlen(join->select_lex->type),
15754
SELECT_LEX *sl= join->unit->first_select();
15755
uint32_t len= 6, lastop= 0;
15756
memcpy(table_name_buffer, STRING_WITH_LEN("<union"));
15757
for (; sl && len + lastop + 5 < NAME_LEN; sl= sl->next_select())
15760
lastop= snprintf(table_name_buffer + len, NAME_LEN - len,
15761
"%u,", sl->select_number);
15763
if (sl || len + lastop >= NAME_LEN)
15765
memcpy(table_name_buffer + len, STRING_WITH_LEN("...>") + 1);
15771
table_name_buffer[len - 1]= '>'; // change ',' to '>'
15773
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15776
item_list.push_back(new Item_string(join_type_str[JT_ALL],
15777
strlen(join_type_str[JT_ALL]),
15779
/* possible_keys */
15780
item_list.push_back(item_null);
15782
item_list.push_back(item_null);
15784
item_list.push_back(item_null);
15786
item_list.push_back(item_null);
15788
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15789
item_list.push_back(item_null);
15791
item_list.push_back(item_null);
15793
if (join->unit->global_parameters->order_list.first)
15794
item_list.push_back(new Item_string("Using filesort",
15797
item_list.push_back(new Item_string("", 0, cs));
15799
if (result->send_data(item_list))
15804
table_map used_tables=0;
15805
for (uint32_t i=0 ; i < join->tables ; i++)
15807
JOIN_TAB *tab=join->join_tab+i;
15808
Table *table=tab->table;
15809
TableList *table_list= tab->table->pos_in_table_list;
15811
char buff1[512], buff2[512], buff3[512];
15812
char keylen_str_buf[64];
15813
String extra(buff, sizeof(buff),cs);
15814
char table_name_buffer[NAME_LEN];
15815
String tmp1(buff1,sizeof(buff1),cs);
15816
String tmp2(buff2,sizeof(buff2),cs);
15817
String tmp3(buff3,sizeof(buff3),cs);
15826
item_list.push_back(new Item_uint((uint32_t)
15827
join->select_lex->select_number));
15829
item_list.push_back(new Item_string(join->select_lex->type,
15830
strlen(join->select_lex->type),
15832
if (tab->type == JT_ALL && tab->select && tab->select->quick)
15834
quick_type= tab->select->quick->get_type();
15835
if ((quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) ||
15836
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
15837
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION))
15838
tab->type = JT_INDEX_MERGE;
15840
tab->type = JT_RANGE;
15843
if (table->derived_select_number)
15845
/* Derived table name generation */
15846
int len= snprintf(table_name_buffer, sizeof(table_name_buffer)-1,
15848
table->derived_select_number);
15849
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15853
TableList *real_table= table->pos_in_table_list;
15854
item_list.push_back(new Item_string(real_table->alias,
15855
strlen(real_table->alias),
15858
/* "type" column */
15859
item_list.push_back(new Item_string(join_type_str[tab->type],
15860
strlen(join_type_str[tab->type]),
15862
/* Build "possible_keys" value and add it to item_list */
15863
if (!tab->keys.is_clear_all())
15866
for (j=0 ; j < table->s->keys ; j++)
15868
if (tab->keys.is_set(j))
15872
tmp1.append(table->key_info[j].name,
15873
strlen(table->key_info[j].name),
15874
system_charset_info);
15879
item_list.push_back(new Item_string(tmp1.ptr(),tmp1.length(),cs));
15881
item_list.push_back(item_null);
15883
/* Build "key", "key_len", and "ref" values and add them to item_list */
15884
if (tab->ref.key_parts)
15886
KEY *key_info=table->key_info+ tab->ref.key;
15887
register uint32_t length;
15888
item_list.push_back(new Item_string(key_info->name,
15889
strlen(key_info->name),
15890
system_charset_info));
15891
length= int64_t2str(tab->ref.key_length, keylen_str_buf, 10) -
15893
item_list.push_back(new Item_string(keylen_str_buf, length,
15894
system_charset_info));
15895
for (store_key **ref=tab->ref.key_copy ; *ref ; ref++)
15899
tmp2.append((*ref)->name(), strlen((*ref)->name()),
15900
system_charset_info);
15902
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15904
else if (tab->type == JT_NEXT)
15906
KEY *key_info=table->key_info+ tab->index;
15907
register uint32_t length;
15908
item_list.push_back(new Item_string(key_info->name,
15909
strlen(key_info->name),cs));
15910
length= int64_t2str(key_info->key_length, keylen_str_buf, 10) -
15912
item_list.push_back(new Item_string(keylen_str_buf,
15914
system_charset_info));
15915
item_list.push_back(item_null);
15917
else if (tab->select && tab->select->quick)
15919
tab->select->quick->add_keys_and_lengths(&tmp2, &tmp3);
15920
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15921
item_list.push_back(new Item_string(tmp3.ptr(),tmp3.length(),cs));
15922
item_list.push_back(item_null);
15926
if (table_list->schema_table && table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
15928
const char *tmp_buff;
15930
if (table_list->has_db_lookup_value)
15932
f_idx= table_list->schema_table->idx_field1;
15933
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15934
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15936
if (table_list->has_table_lookup_value)
15938
if (table_list->has_db_lookup_value)
15940
f_idx= table_list->schema_table->idx_field2;
15941
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15942
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15945
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15947
item_list.push_back(item_null);
15950
item_list.push_back(item_null);
15951
item_list.push_back(item_null);
15952
item_list.push_back(item_null);
15955
/* Add "rows" field to item_list. */
15956
if (table_list->schema_table)
15959
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15960
item_list.push_back(item_null);
15962
item_list.push_back(item_null);
15966
double examined_rows;
15967
if (tab->select && tab->select->quick)
15968
examined_rows= rows2double(tab->select->quick->records);
15969
else if (tab->type == JT_NEXT || tab->type == JT_ALL)
15970
examined_rows= rows2double(tab->limit ? tab->limit :
15971
tab->table->file->records());
15973
examined_rows= join->best_positions[i].records_read;
15975
item_list.push_back(new Item_int((int64_t) (uint64_t) examined_rows,
15976
MY_INT64_NUM_DECIMAL_DIGITS));
15978
/* Add "filtered" field to item_list. */
15979
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15983
f= (float) (100.0 * join->best_positions[i].records_read /
15985
item_list.push_back(new Item_float(f, 2));
15989
/* Build "Extra" field and add it to item_list. */
15990
bool key_read=table->key_read;
15991
if ((tab->type == JT_NEXT || tab->type == JT_CONST) &&
15992
table->covering_keys.is_set(tab->index))
15994
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT &&
15995
!((QUICK_ROR_INTERSECT_SELECT*)tab->select->quick)->need_to_fetch_row)
15999
item_list.push_back(new Item_string(tab->info,strlen(tab->info),cs));
16000
else if (tab->packed_info & TAB_INFO_HAVE_VALUE)
16002
if (tab->packed_info & TAB_INFO_USING_INDEX)
16003
extra.append(STRING_WITH_LEN("; Using index"));
16004
if (tab->packed_info & TAB_INFO_USING_WHERE)
16005
extra.append(STRING_WITH_LEN("; Using where"));
16006
if (tab->packed_info & TAB_INFO_FULL_SCAN_ON_NULL)
16007
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16008
/* Skip initial "; "*/
16009
const char *str= extra.ptr();
16010
uint32_t len= extra.length();
16016
item_list.push_back(new Item_string(str, len, cs));
16020
uint32_t keyno= MAX_KEY;
16021
if (tab->ref.key_parts)
16022
keyno= tab->ref.key;
16023
else if (tab->select && tab->select->quick)
16024
keyno = tab->select->quick->index;
16026
if (keyno != MAX_KEY && keyno == table->file->pushed_idx_cond_keyno &&
16027
table->file->pushed_idx_cond)
16028
extra.append(STRING_WITH_LEN("; Using index condition"));
16030
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
16031
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
16032
quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE)
16034
extra.append(STRING_WITH_LEN("; Using "));
16035
tab->select->quick->add_info_string(&extra);
16039
if (tab->use_quick == 2)
16041
/* 4 bits per 1 hex digit + terminating '\0' */
16042
char buf[MAX_KEY / 4 + 1];
16043
extra.append(STRING_WITH_LEN("; Range checked for each "
16044
"record (index map: 0x"));
16045
extra.append(tab->keys.print(buf));
16048
else if (tab->select->cond)
16050
const COND *pushed_cond= tab->table->file->pushed_cond;
16052
if (session->variables.engine_condition_pushdown && pushed_cond)
16054
extra.append(STRING_WITH_LEN("; Using where with pushed "
16056
if (session->lex->describe & DESCRIBE_EXTENDED)
16058
extra.append(STRING_WITH_LEN(": "));
16059
((COND *)pushed_cond)->print(&extra, QT_ORDINARY);
16063
extra.append(STRING_WITH_LEN("; Using where"));
16068
if (quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
16069
extra.append(STRING_WITH_LEN("; Using index for group-by"));
16071
extra.append(STRING_WITH_LEN("; Using index"));
16073
if (table->reginfo.not_exists_optimize)
16074
extra.append(STRING_WITH_LEN("; Not exists"));
16076
if (quick_type == QUICK_SELECT_I::QS_TYPE_RANGE &&
16077
!(((QUICK_RANGE_SELECT*)(tab->select->quick))->mrr_flags &
16078
HA_MRR_USE_DEFAULT_IMPL))
16080
extra.append(STRING_WITH_LEN("; Using MRR"));
16083
if (table_list->schema_table &&
16084
table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
16086
if (!table_list->table_open_method)
16087
extra.append(STRING_WITH_LEN("; Skip_open_table"));
16088
else if (table_list->table_open_method == OPEN_FRM_ONLY)
16089
extra.append(STRING_WITH_LEN("; Open_frm_only"));
16091
extra.append(STRING_WITH_LEN("; Open_full_table"));
16092
if (table_list->has_db_lookup_value &&
16093
table_list->has_table_lookup_value)
16094
extra.append(STRING_WITH_LEN("; Scanned 0 databases"));
16095
else if (table_list->has_db_lookup_value ||
16096
table_list->has_table_lookup_value)
16097
extra.append(STRING_WITH_LEN("; Scanned 1 database"));
16099
extra.append(STRING_WITH_LEN("; Scanned all databases"));
16101
if (need_tmp_table)
16104
extra.append(STRING_WITH_LEN("; Using temporary"));
16109
extra.append(STRING_WITH_LEN("; Using filesort"));
16111
if (distinct & test_all_bits(used_tables,session->used_tables))
16112
extra.append(STRING_WITH_LEN("; Distinct"));
16114
if (tab->insideout_match_tab)
16116
extra.append(STRING_WITH_LEN("; LooseScan"));
16119
if (tab->flush_weedout_table)
16120
extra.append(STRING_WITH_LEN("; Start temporary"));
16121
else if (tab->check_weed_out_table)
16122
extra.append(STRING_WITH_LEN("; End temporary"));
16123
else if (tab->do_firstmatch)
16125
extra.append(STRING_WITH_LEN("; FirstMatch("));
16126
Table *prev_table=tab->do_firstmatch->table;
16127
if (prev_table->derived_select_number)
16129
char namebuf[NAME_LEN];
16130
/* Derived table name generation */
16131
int len= snprintf(namebuf, sizeof(namebuf)-1,
16133
prev_table->derived_select_number);
16134
extra.append(namebuf, len);
16137
extra.append(prev_table->pos_in_table_list->alias);
16138
extra.append(STRING_WITH_LEN(")"));
16141
for (uint32_t part= 0; part < tab->ref.key_parts; part++)
16143
if (tab->ref.cond_guards[part])
16145
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16150
if (i > 0 && tab[-1].next_select == sub_select_cache)
16151
extra.append(STRING_WITH_LEN("; Using join buffer"));
16153
/* Skip initial "; "*/
16154
const char *str= extra.ptr();
16155
uint32_t len= extra.length();
16161
item_list.push_back(new Item_string(str, len, cs));
16163
// For next iteration
16164
used_tables|=table->map;
16165
if (result->send_data(item_list))
16169
for (SELECT_LEX_UNIT *unit= join->select_lex->first_inner_unit();
16171
unit= unit->next_unit())
16173
if (mysql_explain_union(session, unit, result))
16180
bool mysql_explain_union(Session *session, SELECT_LEX_UNIT *unit, select_result *result)
16183
SELECT_LEX *first= unit->first_select();
16185
for (SELECT_LEX *sl= first;
16187
sl= sl->next_select())
16189
// drop UNCACHEABLE_EXPLAIN, because it is for internal usage only
16190
uint8_t uncacheable= (sl->uncacheable & ~UNCACHEABLE_EXPLAIN);
16191
sl->type= (((&session->lex->select_lex)==sl)?
16192
(sl->first_inner_unit() || sl->next_select() ?
16193
"PRIMARY" : "SIMPLE"):
16195
((sl->linkage == DERIVED_TABLE_TYPE) ?
16197
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16198
"DEPENDENT SUBQUERY":
16199
(uncacheable?"UNCACHEABLE SUBQUERY":
16201
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16203
uncacheable?"UNCACHEABLE UNION":
16205
sl->options|= SELECT_DESCRIBE;
16207
if (unit->is_union())
16209
unit->fake_select_lex->select_number= UINT_MAX; // jost for initialization
16210
unit->fake_select_lex->type= "UNION RESULT";
16211
unit->fake_select_lex->options|= SELECT_DESCRIBE;
16212
if (!(res= unit->prepare(session, result, SELECT_NO_UNLOCK | SELECT_DESCRIBE)))
16214
res|= unit->cleanup();
16218
session->lex->current_select= first;
16219
unit->set_limit(unit->global_parameters);
16220
res= mysql_select(session, &first->ref_pointer_array,
16221
(TableList*) first->table_list.first,
16222
first->with_wild, first->item_list,
16224
first->order_list.elements +
16225
first->group_list.elements,
16226
(order_st*) first->order_list.first,
16227
(order_st*) first->group_list.first,
16229
(order_st*) session->lex->proc_list.first,
16230
first->options | session->options | SELECT_DESCRIBE,
16231
result, unit, first);
16233
return(res || session->is_error());
6257
16237
static void print_table_array(Session *session, String *str, TableList **table,
6258
16238
TableList **end)